Abstract
Risultati

Analisi degli algoritmi: 
Analisi

Bubblesort vs Quicksort

Dati raccolti da: Sucharita Kamath,Christian Allain, Keyur Dalal
 

Abstract

Questo report descrive i risultati ottenuti testando due diversi algoritmi sullo stesso gruppo di dati per comparare la loro efficienza. L'obiettivo è comparare la complessità per lo spazio e il tempo degli algoritmi e stimarne la vicinanza con la teoria.
Gli algoritmi selezionati sono il BubbleSort e il QuickSort. Vogliamo comparare questi algoritmi per la loro diversa complessità rispetto al tempo: rispettivamente: O(n2), O(n lg n).

I gruppi di dati da ordinare hanno diversi ranges e grandezze. Ogni algoritmo di sorting è testato su gruppi di 10, 100, 1000, 10.000, 100.000 numeri casuali in ranges che variano da [0:9], [0:99], [0:999], [0:9999]. La procedura è ripetuta usando un array ordinato di elementi per verificare la teoria per il caso migliore di ogni algoritmo.

Risultati

La seguente tavola mostra i risultati ottenuti per i due algoritmi e per i differenti ranges e numero di elementi.


 


 
 


 

Analisi

I risultati si accostano alla teoria in tutti i casi.
Come ci si aspettava, Bubble sort è l'algoritmo con il consumo di tempo più grande.

La seguente tavola mostra un esempio di complessità rispetto allo spazio dei due algoritmi.
 

Algoritmo Spazio
Bubble 716 K
Quick 720 K

I risultati ottenuti qui per un array di 100.000 valori tra 1 e 9 sono rappresentativi della uguale complessità rispetto allo spazio dei due algoritmi, in accordo con la teoria.

Un commento che vale per entrambi gli algoritmi è che le funzioni di input e output degli algoritmi prendono più del tempo di esecuzione dell'algoritmo stesso (almeno il 70% del tempo totale).

Array già ordinati:

I risultati nella seguente tabella sono per un set di dati già ordinati.
 

Algoritmo Tempo in secondi
Bubble 33.53
Quick 2.20



back