3 pagine in totale: <<Indietro 1 [2] 3 Avanti >>
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 subUtilizzando 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.
3 pagine in totale: <<Indietro 1 [2] 3 Avanti >>
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!