Informatica I - Esercizi bubbleSort

Esercizio di laboratorio

Argomento: algoritmi di ordinamento, ordinamento di stringhe

Realizzare un algoritmo di ordinamento per dati di un array che procede in questo modo:

• Si scandisce l'array a partire dall'ultimo indice fino al primo indice, e si confronta ogni coppia di elementi adiacenti, scambiandoli se non rispettano il loro ordinamento relativo (cioè se il valore nell'elemento di indice superiore è maggiore di quello nell'elemento di indice inferiore).
• Al termine di questa prima scansione, il valore minimo contenuto nell'intero array è contenuto nell'elemento di indice 0 dell'array.
• Il passo successivo è identico al precedente, ma termina dopo aver esaminato l'elemento di indice 1: al termine di questa seconda scansione, anche l'elemento di indice 1 dell'array contiene l'elemento corretto.
• Si itera il procedimento fino al completo ordinamento dell'array.

Questo algoritmo prende il nome di ordinamento a bolle (bubbleSort). Infatti, se si considera l'array come se fosse disposto verticalmente, con la cella di indice 0 in alto, lo spostamento di valori effettuato dall'algoritmo è simile al movimento di bolle che gorgogliano verso l'alto.

Soluzione

Il metodo bubbleSort, descritto nel testo dell'esercizio, necessita di due cicli annidati. Inoltre abbiamo isolato l'operazione di scambio tra due elementi dell'array in un metodo ausiliario swap.

Prestare attenzione al fatto che il confronto di ordinamento tra stringhe avviene attraverso il metodo compareTo.

// ------------ alg. di ordinamento: bubbleSort --------

public static void bubbleSort(String[] v, int vSize){ for (int i = 0; i < vSize-1; i++) //attenzione alla formulazione
for (int j = vSize-1; j > i; j--) //di questi due cicli
if (v[j].compareTo(v[j-1]) < 0)
swap(v, j, j-1);}

private static void swap(String[] v, int i, int j){ String s = v[i];
v[i] = v[j];
v[j] = s;}