3 pagine in totale: <<Indietro 1 2 [3]
Dall'Inghilterra con furore
Un altro algoritmo generalmente noto è il QuickSort , la cui felice e fortunata scoperta è dovuta ad un ricercatore inglese, Sir Tony Hoare. Questo è un tipo di algoritmo molto efficiente che segue la logica divide and conquer per ordinare un gruppo di elementi.
Anche se vi sono diverse varianti del QuickSort le fasi generalmente utilizzate sono:
- Selezione di un elemento della lista. Questo verrà utilizzato come elemento cardine ( pivot ) durante l'esecuzione
- Scansione della lista al fine di collocare gli elementi maggiori del pivot alla sua destra e quelli minori alla sua sinistra. Anche in questo caso lo spostamento avviene tramite scambio o swap degli elementi
- Divisione della lista in due parti: una (sinistra) con gli elementi minori del pivot e l'altra con gli elementi più grandi
- Ripetizioni delle tre fasi su ogni sotto-lista fino a quando tutti gli elementi non sono in ordine
In questo esempio verranno utilizzati il pivot centrale (potrebbe essere fisso su una posizione o selezionato a caso) e la tecnica della ricorsione (anche se questo è lo standard vi sono implementazioni che non utilizzano la ricorsione).
sub quickSort(byVal primoElemento,byVal ultimoElemento)
dim limiteInferiore,limiteSuperiore, separatoreMediano
limiteInferiore = primoElemento
limiteSuperiore = ultimoElemento
separatoreMediano =arrayRandom((primoElemento + ultimoElemento) / 2)
do
'tutti gli elementi a sinistra del mediano dovrebbero essere di valore inferiore
'quindi trova la posizione del primo elemento con valore maggiore del mediano
'tra quelli alla sua sinistra
while arrayRandom(limiteInferiore) < separatoreMediano
limiteInferiore = limiteInferiore + 1
wend
'tutti gli elementi a destra del mediano dovrebbero essere di valore maggiore
'quindi trova la posizione del primo elemento con valore inferiore del mediano
'tra quelli alla sua destra
while (arrayRandom(limiteSuperiore) > separatoreMediano)
limiteSuperiore = limiteSuperiore - 1
wend
'se il limiteInferiore è minore del superiore scambia gli elementi
if limiteInferiore <= limiteSuperiore Then
if limiteInferiore < limiteSuperiore Then
call invertiValore(limiteInferiore, limiteSuperiore)
end if
'incrementa/decrementa i limiti
limiteInferiore = limiteInferiore + 1
limiteSuperiore = limiteSuperiore - 1
end if
'esce dal ciclo quando il limite inferiore è più grande del maggiore
loop while (limiteInferiore <= limiteSuperiore)
if primoElemento < limiteSuperiore Then
call quickSort(primoElemento, limiteSuperiore)
end if
if limiteInferiore < ultimoElemento Then
call quickSort(limiteInferiore, ultimoElemento)
end if
end subVeloce ma consuma!
In genere il QuickSort è molto efficiente con una misurazione media di passaggi uguale a O(n log n) ma se il gruppo di elementi è quasi in ordine all'inizio la sua performance non è eccezionale, specialmente se si utilizza un pivot corrispondente alla testa di ogni lista. Nel peggiore dei casi può arrivare a O(n2), come l'Insertion Sort o forse addirittura come il 'primitivo' BubbleSort!
Spesso conviene utilizzare il QuickSort per ordinare grandi gruppi di elementi, ma bisogna non dimenticare comunque che la tecnica delle ricorsione da esso ampiamente utilizzata può catastroficamente consumare lo spazio di stack in condizioni limite.
Per finire
Un suggerimento valido per chi voglia utilizzare in situazioni reali gli algoritmi allegati è quello di rimuovere le variabili che misurano il numero di scambi e di comparazioni, poichè la loro presenza nel codice riduce notevolmente la performance del codice. Un semplice incremento di variabile come il seguente
miaVariabile = miaVariabile + 1in VBScript causa rallentamenti del codice poichè questo linguaggio non può utilizzare niente di meglio del tipo variant , anche quando un integer sarebbe piu` efficiente. A questo si aggiunga che le variabili in questione sono globali.
Ci sono molti altri algoritmi che vale la pena di analizzare. Nel frattempo potrebbe valer la pena di iniziare a dare un'occhiata in giro per il web dove si possono trovare maggiori informazioni, altri test, misurazioni più sofisticate e alcune utili applet per visualizzare concretamente l'azione dell'ordinamento.
Approfondimenti
- Scarica subito l'allegato (10 kb)
- #44 - Ordinare alfabeticamente i files di una directory 1/3 (bubble sort)
- #45 - Ordinare alfabeticamente i files di una directory 2/3 (select sort)
- #46 - Ordinare alfabeticamente i files di una directory 3/3 (quick sort)
3 pagine in totale: <<Indietro 1 2 [3]
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!