Follow

L'algoritmo di Bubble Sorting in azione.

Insertion Sort e Selection Sort non si sono rivelati all’altezza delle nostre aspettative e noi ci ritroviamo ancora senza un algoritmo efficente per ordinare, o meglio: sappiamo ordinare le tracce di un album, oppure i CD di un apiccola collezione domestica, ma avremo molte difficoltà nell’ordinare in ordine di età gli abitanti di Roma o i volumi di un agrande biblioteca.

Dobbiamo proseguire la nostra ricerca, cambiamo approccio, questa volta il nostro tentativo cade sul Bubble Sort.

Il Bubble Sort deriva il suo nome dal comportamento degli elementi da ordinare sotto l’effetto di questo algoritm: essi infatti sembrano “risalire” l’array come bollicine nell’acqua minerale (si nota bene nell’animazione a lato).

BubbleSort(array[], elemN)
  alto = elemN
  changed = True
  while (alto > 0 and changed = True) :
    change = False
    for i = 0 to alto - 1 :
      if (array[i] > array[i + 1]) :
        tmp = array[i]
        array[i] = array[i + 1]
        array[i+1] = tmp
        changed = True
    alto = alto - 1

Il meccanismo di fondo è molto semplice: finchè alto (che l’indice che indica la “sommità” dell’array) rimane maggiore di zero ed è stato effettuato almento uno scambio (indicato dalla variabile changed) inizio una scansione dall’inizio fino ad alto dell’array e ogni volta che trovo un elemento maggiore del successivo, scambio i due elementi di posto.

E’ chiaro quindi che il Bubble Sort ha la capacità di accorgersi se un array è già ordinato (infatti se un array è ordinato non entra mai nel if per resettare la variabile changed e questo provoca l’uscita dal while) nel qual caso effettuerà soltanto la scansione di controllo con consto O(n).

Il caso peggiore è ovviamente un array ordinato al contrario. In questo caso infatti ogni scansione serve a posizionare con scambi successivi un solo elemento. Quindi avremo che in totale l’algoritmo ha costo O(n²).

Esatto anche lui. Anche il Bubble Sort si comporta come l’Insertion e il Selection Sort. Nessun vantaggio allora?

In realtà no. Un piccolo passo l’abbiamo fatto. Il Bubble Sort ci permette, con la sua capacità di fermarsi quando un array è ordinato, di eseguire inserimenti ordinati (ovvero inserimenti che mantengono l’ordine) con costo costante nel caso peggiore di O(n). Infatti non dobbiamo fare altro che sfruttare lo stesso meccanismo per scambiare elemento dopo elemento l’elemento da inserire (inizialmente in testa) fino alla sua posizione naturale.

Quindi ora, dato un array ordinato, sappiamo fare inserimenti ordinati, ma dobbiamo trovare ancora un metodo per ordinare l’array di partenza.

La nostra ricerca non è finita qui. Possiamo fare di meglio. Proveremo con il Quick Sort. Sperando che sia Quick.