Ordinamento 1: bubble sort, selection sort e insertion sort

Il selection sort fa esattamente 45 confronti su qualsiasi lista di 10 valori, che la lista parta mescolata o già in ordine.

Mettere le cose in ordine

Ordinare significa risistemare una lista in modo che i valori vadano dal più piccolo al più grande (o per nome, data, prezzo, qualsiasi ordine in cui si possa confrontare). È uno dei lavori più comuni di un computer: i contatti di un telefono, i risultati di una ricerca in ordine di pertinenza, una colonna di un foglio di calcolo ordinata per data. Ordinare rende anche più facili altri lavori. Come ha mostrato l'unità precedente, in una lista ordinata si può cercare con la ricerca binaria, e i doppioni stanno uno accanto all'altro.

Questa unità presenta tre metodi semplici. Tutti e tre confrontano due valori alla volta e spostano i valori dentro la stessa lista. Sono brevi da scrivere e facili da seguire, e tutti e tre rallentano molto sulle liste lunghe. Capire perché rallentano è la migliore preparazione ai metodi più veloci della prossima unità. Lungo tutta l'unità contiamo due cose: i confronti (chiedersi «questo valore è più grande di quello?») e gli scambi (due valori che si scambiano di posto).

Bubble sort: scambia i vicini fuori ordine

Il bubble sort percorre la lista confrontando ogni coppia di vicini. Quando quello a sinistra è più grande, li scambia. Dopo una passata completa, il valore più grande è stato portato passo dopo passo fino in fondo a destra, come una bolla che sale, e non dovrà più muoversi. La passata successiva può fermarsi un posto prima. Un miglioramento comune è accorgersi di una passata senza nessuno scambio: vuol dire che tutto è già in ordine, quindi l'ordinamento può fermarsi prima.

Seguilo sulla lista [5, 1, 4, 2, 8]. La prima passata confronta 5 e 1 (scambio), 5 e 4 (scambio), 5 e 2 (scambio), 5 e 8 (niente): ora la lista è [1, 4, 2, 5, 8] e 8 è al suo posto. La seconda passata confronta 1 e 4, 4 e 2 (scambio), 4 e 5, e dà [1, 2, 4, 5, 8]. La terza passata confronta 1 e 2, poi 2 e 4, non fa scambi e si ferma. In tutto: 4 + 3 + 2 = 9 confronti e 4 scambi.

function bubbleSort(a) {
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - pass; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];  // scambio
        swapped = true;
      }
    }
    if (!swapped) break;  // già ordinata
  }
  return a;
}

Selection sort: trova il più piccolo e mettilo dopo

Il selection sort funziona come molte persone ordinano le carte che hanno in mano. Scorri tutta la lista cercando il valore più piccolo e scambialo nella prima posizione. Poi scorri il resto cercando il più piccolo tra quelli rimasti e scambialo nella seconda posizione, e così via. Su [5, 1, 4, 2, 8] la prima scansione trova 1 e lo scambia con 5; la seconda trova 2 e lo scambia con 5; le ultime due trovano 4 e 5 già al loro posto. Sono solo 2 scambi, ma le scansioni confrontano comunque 4 + 3 + 2 + 1 = 10 volte.

Il selection sort non si ferma mai prima. Anche su una lista già ordinata deve controllare ogni valore rimasto per essere sicuro di avere il più piccolo. Per n valori i confronti sommano sempre (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. Per 10 valori sono 45; per 100 valori, 4950; per 1000 valori, 499500. Il suo punto di forza è il piccolo numero di scambi: al massimo n − 1, il che conta quando spostare un valore costa molto.

Insertion sort: fai scivolare ogni nuovo valore al suo posto

L'insertion sort tiene ordinata la parte sinistra della lista e la allarga un valore alla volta. Prende il valore successivo e lo sposta a sinistra, scambiandolo con il vicino, finché il vicino non è più grande. A quel punto il valore è al suo posto tra quelli ordinati. Su una lista già quasi in ordine, ogni nuovo valore si sposta solo di un passo o due, quindi lì l'insertion sort è velocissimo. Su [5, 1, 4, 2, 8] fa 7 confronti e 4 scambi.

Contare gli scambi: le inversioni

C'è un modo elegante per prevedere quanti scambi servono al bubble sort e all'insertion sort. Conta le inversioni: le coppie di valori che sono nell'ordine sbagliato l'uno rispetto all'altro. In [5, 1, 4, 2, 8] le inversioni sono (5, 1), (5, 4), (5, 2) e (4, 2), quattro in tutto. Ogni scambio tra due vicini fuori ordine corregge esattamente un'inversione e non ne crea altre, quindi entrambi i metodi fanno esattamente 4 scambi. Una lista invertita di n valori ha tutte le coppie invertite, n(n − 1)/2 inversioni, ed è il caso peggiore.

Ogni cella indica confronti / scambi. La lista di esempio è [5, 1, 4, 2, 8]. Qui il bubble sort è la versione che si ferma dopo una passata senza scambi.

I tre metodi hanno lo stesso punto debole. Nel caso peggiore ognuno confronta più o meno ogni coppia di valori, circa n²/2 confronti. Raddoppia la lista e il lavoro diventa quattro volte tanto. Una lista dieci volte più lunga vuol dire cento volte il lavoro. Per qualche decina di valori conta poco; per un milione è un'impresa senza speranza, e la prossima unità mostra come fare molto meglio.