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:

• illustrare il funzionamento step by step dei diversi algoritmi
• fornire funzioni pronte all'uso con algoritmi di ordinamento
• misurarne l'efficienza

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.