Ordinamento 2: merge sort e quicksort

Ordinare un milione di valori confrontando ogni coppia richiede circa 500 miliardi di confronti; al merge sort ne servono circa 20 milioni.

Dividi il problema, risolvi le metà

I metodi dell'unità precedente lavorano su tutta la lista insieme e lo pagano con circa n² confronti. I due metodi di questa unità seguono un piano diverso, chiamato divide et impera. Dividi la lista in parti più piccole, ordina ogni parte con lo stesso metodo e poi unisci le parti ordinate. La divisione continua finché una parte ha un solo valore o nessuno, e una lista di un solo valore è già ordinata. Poiché il metodo richiama sé stesso su liste più piccole, è ricorsivo (l'unità 6 esamina la ricorsione nel dettaglio).

Merge sort: il lavoro sta nella fusione

Il merge sort taglia la lista a metà, ordina la metà sinistra, ordina la metà destra e fonde le due metà ordinate in una sola. La parte ingegnosa è la fusione. Due liste ordinate si possono unire guardando solo i loro primi valori. Confronta i due valori in testa, scrivi il più piccolo e vai oltre. Ripeti finché una lista è vuota, poi copia ciò che resta dell'altra. Fondere [1, 4, 7] e [2, 3, 8] dà 1 (1 contro 2), 2 (4 contro 2), 3 (4 contro 3), 4 (4 contro 8), 7 (7 contro 8), e poi si copia 8: 5 confronti per 6 valori. Una fusione di due liste con n valori in tutto non richiede mai più di n − 1 confronti.

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (right[j] < left[i]) out.push(right[j++]);
    else out.push(left[i++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}

function mergeSort(a) {
  if (a.length <= 1) return a;          // già ordinata
  const mid = Math.floor(a.length / 2);
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

Perché è veloce? Immagina i dimezzamenti come livelli. Una lista di 8 valori si divide in 2 liste da 4, poi in 4 liste da 2, poi in 8 liste da 1: tre livelli, perché 8 si può dimezzare 3 volte. A ogni livello, tutte le fusioni insieme toccano ogni valore una volta, quindi un livello costa al massimo circa n confronti. Con log₂ n livelli il totale è circa n log₂ n. Per un milione di valori sono circa 20 milioni di confronti, contro circa 500 miliardi per i metodi che confrontano coppia per coppia. Divisa in [38, 27, 43, 3] e [9, 82, 10], come nel laboratorio, la lista [38, 27, 43, 3, 9, 82, 10] richiede 14 confronti; il codice qui sopra la divide in 3 e 4 e ne richiede 13.

Il prezzo è la memoria. La fusione ha bisogno di un posto dove scrivere il risultato, quindi il merge sort usa una seconda lista grande quanto l'input. Il merge sort è anche stabile: i valori che risultano uguali nel confronto mantengono il loro ordine originale, perché quando i due valori in testa sono uguali la fusione prende dalla lista sinistra. Questo conta quando ordini una tabella per una colonna dopo l'altra, per esempio per città e poi per nome.

Quicksort: dividi attorno a un pivot

Il quicksort divide la lista in un altro modo. Sceglie un valore, il pivot, e risistema la lista in modo che tutto ciò che è più piccolo del pivot venga prima e tutto il resto dopo. Questo passo si chiama partizione. Ora il pivot è al suo posto definitivo, e le due parti si possono ordinare separatamente con lo stesso metodo. Dopo non serve nessuna fusione, perché ogni valore a sinistra è già più piccolo di ogni valore a destra.

Il laboratorio usa una versione comune nei manuali che prende come pivot l'ultimo valore di ogni parte. Su [5, 1, 4, 2, 8] il pivot 8 viene confrontato con gli altri quattro valori, tutti più piccoli, quindi 8 resta in fondo. La parte successiva [5, 1, 4, 2] usa il pivot 2: solo 1 è più piccolo, quindi dopo due scambi la lista è [1, 2, 4, 5, 8]. Un altro confronto sistema [4, 5]. In tutto: 8 confronti e 2 scambi.

Quando il pivot cade vicino al centro, ogni divisione dimezza il problema e il quicksort fa circa n log₂ n confronti, come il merge sort. Inoltre lavora dentro la lista originale, senza una seconda copia. Ma un pivot sbagliato fa male. Se la lista è già ordinata e il pivot è sempre l'ultimo valore, ogni divisione stacca un solo valore, e il quicksort ricade a circa n²/2 confronti: 10 per [1, 2, 3, 4, 5], gli stessi del selection sort. Le librerie reali evitano il problema scegliendo il pivot con più cura, per esempio a caso o come valore di mezzo fra tre campioni.