Quando si deve gestire un grande numero di dati è spesso importante ordinarli secondo un criterio prestabilito per poter, ad esempio, cercare dati di un certo tipo, raggrupparli o desumere da essi altri dati.
A questo scopo sono stati escogitate varie metodologie che possono più o meno efficacemente essere implementate nei vari linguaggi di programmazione. Molti linguaggi anzi sono forniti al programmatore con librerie già dotate delle procedure necessarie. Javascript è stato progettato come linguaggio interpretato leggero e flessibile da incorporare nei browser e, come si dirà nel capitolo successivo, prevede metodi di questo genere solo per le stringhe alfanumeriche. Il più delle volte spetta quindi al programmatore redigere le funzioni necessarie all'ordinamento dei propri dati.
Nel seguente esempio si propongono due degli algoritmi più usati noti con i nomi di Bubble Sort e Quick Sort, applicati all'ordinamento di una serie di numeri interi generati casualmente. L'esempio permette anche di confrontare l'efficienza dei due algoritmi in termini di tempi di elaborazione misurati in millisecondi.
Per vedere il codice Javascript usato nell'esempio, cliccare sul bottone.
Entrambi gli algoritmi citati operano su gruppi di dati omogenei e confrontabili che conviene quindi immettere in un array. Nell'esempio 22 i dati sono semplicemente dei numeri naturali casuali, generati dalla funzione genera() e immessi nell'array numeri dimensionato sulla quantità di elementi generati.
L'algoritmo Bubble Sort è abbastanza spontaneo: consiste nel confrontare successivamente
ogni elemento dell'array con tutti i successivi. Se, come si suppone nell'esempio, si
vuole un ordinamento crescente, se un elemento numeri[i] è maggiore
dell'elemento successivo numeri[j], gli elementi si scambiano di posto.
Il nucleo dell'algoritmo è quindi il doppio ciclo
for (i=0; i<quanti-1; i++)
for (j=i+1; j<quanti; j++)
if (numeri[j]<numeri[i])
scambia(i,j);
Al termine di questo doppio ciclo l'array risulta ordinato.
L'algoritmo QuickSort, come dice il nome, è molto più veloce ma più sofisticato perché è ricorsivo.
Si sceglie uno qualunque degli elementi dell'array, ad esempio quello in posizione centrale; questo elemento funge da pivot cioè da cardine di confronto. Partendo dal primo elemento si sale (indice i++) fino a che non se ne trova uno che supera il pivot e partendo dall'ultimo elemento si scende (indice j--) finché non se ne trova uno che è inferiore al pivot. Se i≤j, gli elementi individuati si scambiano di posto e si continua fino a che i supera j. Al termine di questa passata gli indici i e j suddividono l'array in due sottogruppi: nelle posizioni a sinistra di j (j incluso) ci sono i numeri minori del pivot, nelle posizioni a destra di i (i incluso) ci sono i numeri maggiori del pivot. A questo punto si applica ricorsivamente l'algoritmo ad ognuno dei due sottogruppi riordinandoli al loro interno. Ognuno dei due sottogruppi cioè viene ulteriormente suddiviso in due parti in ognuna delle quali si individua un pivot e si scambiano gli elementi fino ad ottenere un ordinamento delle stesse. Si prosegue fino a che non rimangono sottogruppi formati da un solo elemento.
Il nucleo dell'algoritmo è quindi la funzione ricorsiva
function qs(primo,ultimo)
{
// pivot: numero in posizione centrale tra primo e ultimo
var pivot = numeri[parseInt((primo+ultimo)/2)];
var i = primo;
var j = ultimo;
do
{
while(numeri[i]<pivot) i++;
while(pivot<numeri[j]) j--;
if(i<=j)
{
scambia(i,j);
i++;
j--;
}
} while (j>=i);
// dopo questa passata, a sinistra della posizione j ci sono i numeri minori del pivot
// a destra della posizione i ci sono i numero maggiori del pivot
if (primo<j) qs(primo,j); // riordino dei numeri in posizione minore di j
if (i<ultimo) qs(i,ultimo); // riordino dei numeri in posizione maggiore di i
}
Al termine di tutte le ricorsioni l'array risulta ordinato.
La seguente pagina mostra esplicitamente il funzionamento dell'algoritmo Quick Sort, evidenziandone i passaggi.