Algoritmi di ordinamento

Quante volte abbiamo dovuto mettere a posto un array o un recordset senza poter contare sulle capacità di ordinamento di SQL? La risposta dipende dal tipo lavoro che facciamo, ma le probabilità che prima o poi ci troviamo in questa situazione sono notevoli.

Mettiamo il caso in cui i dati attinti da una tabella di database con valori criptati debbano essere visualizzati in un certo ordine. In questa situazione non possiamo utilizzare SQL per sistemare i dati perchè l'ordinamento avverrebbe su criteri sbagliati (per esempio la lettera 'A' non sarebbe rappresentata come tale ma attraverso una stringa, diversa a seconda dell'algoritmo e della chiave utilizzati). In questo caso abbiamo bisogno di un algoritmo di ordinamento per il recordset restituito.

Ci sono molti modi (algoritmi) per mettere ordine in una lista. Alcuni sono molto efficienti, altri affatto. Alcuni sono noti (BubbleSort, QuickSort) altri meno.

Attraverso questo ed altri articoli cercheremo di:

Il vecchio lento BubbleSort

Forse il più famoso e notoriamente uno dei meno efficienti algoritmi (non il peggiore comunque) è il BubbleSort (noto anche come Sinking Sort, perchè il valore più grande 'affonda' o Exchange Sort, perchè completamente basato sullo scambio di elementi). In genere è molto lento ma anche uno dei più semplici da capire (e illustrare).

Il principio su cui si basa è quello della comparazione di due elementi vicini e dello scambio della loro posizione, se necessario. Ciò comporta che l'intera serie degli oggetti debba essere scandita diverse volte fino a quando tutti gli oggetti adiacenti non siano in ordine.

Swap!

Il cuore di questo algoritmo consiste nello scambio di elementi adiacenti quando il primo (da sinistra per liste in ordine crescente) è maggiore del secondo. Poichè lo scambio o swap è parte comune ad altri algoritmi che tratteremo, è stato messo in una subroutine a parte:

sub invertiValore(ByVal elementoSinistro, ByVal elementoDestro)

  dim temp
  temp = arrayRandom(elementoSinistro)

  arrayRandom(elementoSinistro) = arrayRandom(elementoDestro)
  arrayRandom(elementoDestro) = temp

end sub

Le righe seguenti mostrano il BubbleSort in azione su un array monodimensionale. È possibile testare l'efficienza dell'algoritmo scaricando i file di esempio e installandoli sul proprio web-server. Cambiando il numero di elementi verrà mostrato il tempo di esecuzione richiesto e il rapporto tra quantità e tempo.

sub bubblesort()

  dim indiceEsterno,indiceAnnidato

  'limite per l'array esterno, ad ogni ciclo decrementato di uno
  for indiceEsterno = (numElementi - 1) to 0 step -1

    'ciclo interno dal primo elemento al limite superiore
    for indiceAnnidato = 1 to indiceEsterno

      'scambia gli elementi se il primo è più grande
      if arrayRandom(indiceAnnidato-1) > arrayRandom(indiceAnnidato) then

        call invertiValore(indiceAnnidato-1,indiceAnnidato)

      end if
    next
  next

end sub

Dal codice si vede che ci sono due cicli annidati: un indice interno (indiceAnnidato) che corre attraverso l'array comparando elementi adiacenti e un indice esterno (indiceEsterno) il quale forza l'indice interno a ripassare attraverso l'array. Ad ogni ciclo esterno l'indice viene decrementato di uno perchè l'elemento più grande dell'array è stato messo nell'ultima posizione quindi non è necessario ricontrollarla. In questo modo l'efficienza del 'BubbleSort puro' è leggermente migliorata.

O(n2)...

La misura dell'esecuzione di quest'algoritmo è generalmente O(n2): ciò significa che il numero di scambi di elementi è proporzionale a N al quadrato (in pratica, raddoppiando il numero degli elementi N il programma richiederà in media un tempo di esecuzione quattro volte maggiore). Questo assunto cambia se la lista è quasi in ordine all'inizio; BubbleSort in quel caso non è poi così male anche se esistono algoritmi migliori anche per piccole liste come l'Insertion Sort per esempio.

Emerging Sort?

Se il BubbleSort è un Sinking Sort (i primi elementi a essere messi in ordine sono i più grandi e vanno a fondo della lista), con un po' di fantasia possiamo considerare l'Insertion Sort un tipo di Emerging Sort. Infatti in questo caso le posizioni propriamente occupate saranno le prime, cioè quelle più superficiali, se proprio vogliamo mantenere il paragone...

La differenza che comunque salta più all'occhio se compariamo il BubbleSort con l'InsertionSort è la presenza del ciclo crescente nel ultimo mentre nel primo la scansione principale degli elementi è inversa.

Un'altra differenza è la maniera in cui avviene lo spostamento dei valori: il tipo di scambio in questo caso non usa una variabile di buffer ma attraverso uno spostamento graduale.

sub insertionSort(byRef arrayDaOrdinare)

  dim limiteSuperiore
  'trova il limite superiore dell'array
  limiteSuperiore = ubound(arrayDaOrdinare)

  dim limiteInferiore, valoreDestro, elementoSinistro

  'scorre lungo l'array dal primo all'ultimo elemento
  for limiteInferiore = 1 to limiteSuperiore

    valoreDestro = arrayDaOrdinare(limiteInferiore)
    elementoSinistro = limiteInferiore-1
    do while (elementoSinistro >= 0)
      'se l'elemento sinistro è piu` grande del destro
      if arrayDaOrdinare(elementoSinistro) > valoreDestro then
        'da all'elemento destro il valore del sinistro
        arrayDaOrdinare(elementoSinistro+1) = arrayDaOrdinare(elementoSinistro)
        'decrementa l'indice sinistro
        elementoSinistro = elementoSinistro - 1

      else
        exit do
      end if
     
    loop

    arrayDaOrdinare(elementoSinistro+1) = valoreDestro
  next
end sub

Utilizzando i file allegati e giocando un pò con i valori, si potrà notare che seppure piu` veloce del Bubble Sort, con questo algoritmo siamo di nuovo alla misura di O(n2). La perdita di efficienza in seguito al raddoppio del numero degli elementi è infatti ancora quadratica.

  Continua...