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 subLe 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 subDal 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.
Attenzione: Questo articolo contiene un allegato
Contenuti dell'articolo
- Galleria fotografica dinamica con ASP.NET AJAX
- Usare Search come un servizio nei tuoi siti e nei tuoi client
- Mappe nel tuo sito con Virtual Earth
- Integrare Windows Live ID, Contacts e Presence API nelle tue applicazioni
- Introduzione ai cloud based service con Windows Live Services
- Realizzare un custom extender AJAX con ASP.NET 3.5
- Tracciare le modifiche ai dati e allineare i datawarehouse con il Change Data Capture in SQL Server 2008
- Le nuove caratteristiche di IIS 7.0 per sviluppatori e sistemisti
Aggiungi un nuovo commento »»»
Per inserire un commento, devi registrarti alla nostra community.
Difficoltà
Stampa 
Download
10annidi.ASPItalia.com: iscriviti alla competizione e vinci fantastici premi ogni mese!
