Corso di Programmazione in Java – Esercizio n° 005
Esercizio n° 005
Problema dell’ordinamento di un
array: Il metodo Bubble Sort.
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Esercizio n° 005
L’ordinamento di un array: Bubble Sort
Da un array di 10 elementi di tipo int, si vuole restituire lo stesso
array ordinato in ordine crescente. Fornire sia il diagramma di
flusso che il relativo codice Java.
Quindi: Se in input abbiamo
Es. array[0]=15; array[1]=10; array[2]=21; array[3]=5;
L’array da restituire sarà il seguente:
array[0]=5; array[1]=10; array[2]=15; array[3]=21;
Il problema dell’ordinamento di un array è uno dei problemi
informatici più famosi: tutt’oggi ricercatori stanno studiano nuovi
algoritmi con l’obiettivo di trovare il metodo più veloce.
Noi vedremo uno dei metodi classici: l’algoritmo Bubble Sort
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Esercizio n° 005
Come funziona il metodo Bubble Sort
Dato un array si prende l’elemento nella prima posizione e lo si confronta
con quello in seconda posizione. Se il primo è maggiore del secondo, si
scambiano di posizione; altrimenti si prosegue confrontando il secondo
elemento con il terzo e così via…
Es.: supponiamo di voler ordinare questo array: 15 6
4 10 11
15
6
4
10
11
2
6
4
10 15
11
2
6
15
4
10
11
2
6
4
10 11
15
2
6
4
15 10
11
2
6
4
10 11
2
15
2
Quando raggiungo la fine dell’array l’elemento più grande è stato messo in
ultima posizione; a questo punto riparto da primo e ripeto la stessa procedura,
fermandomi al penultimo elemento dell’array..
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Esercizio n° 005
Soluzione dell’esercizio n° 005
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Esercizio n° 005
Diagramma di flusso del Bubble Sort
Inizio
i=0
temp = 0
i < j-1
falso
Array x
j = lunghezza array-1
j>0
falso
Fine
falso
vero
x[i] > x[i+1]
vero
temp = x[i]
x[i] = x[i+1]
vero
x[i+1] = temp
j= j-1
Istituto Statale di Istruzione Superiore “F. Enriques”
i= i + 1
Corso di Programmazione in Java – Esercizio n° 005
Traduzione in Java del D.d.F.
public void main (String[] args) {
int prova [] = {5,18,46,52,83,37,22,51,3,61};
int temp = 0;
int j = prova.length;
System.out.print(“Array non ordinato: ”);
for (i=0; i<prova.lenght; i++) System.out.print(“ ” + prova[i] );
while ( j > 0 ){
for ( int i = 0; i < j-1; i++ ){
if ( prova[i] > prova[i+1] ){
temp = prova[i];
prova[i] = prova[i+1];
prova[i+1] = temp;
};
};
j--;
};
System.out.print(“Array ordinato: ”);
for (i=0; i<prova.lenght; i++) System.out.print(“ ” + prova[i]);
};
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Esercizio n° 005
Bubble Sort in azione
j
5
5
5
5
5
i
0
1
2
3
4
Array Corrente
15 6 4 10 11 2
6 15 4 10 11 2
6 4 15 10 11 2
6 4 10 15 11 2
6 4 10 11 15 2
6 4 10 11 2 15
j
4
4
3
2
1
i
0
3
3
1
0
4
4
4
4
2
Array Corrente
6 10 11 2
6 10 2 11
6 2 10 11
2 6 10 11
4 6 10 11
15
15
15
15
15
Nella tabella sono indicati i valori degli indici i e j del passo corrispondente,
relativi al codice Java della diapositiva precedente.
Sono inoltre evidenziati i valori che vengono scambiati.
Istituto Statale di Istruzione Superiore “F. Enriques”