Informatica 2 Liceo Scientifico Scienze Applicate/BubbleSort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
Nessun oggetto della modifica |
||
Riga 8:
[[File:Bubblesort1.png|Bubblesort 1^ passata]]<br />
come si vede, alla fine della prima passata il vettore e' composto da due parti una ordinata (colore verde) che contiene il numero piu' piccolo (2) e una che deve essere ancora ordinata, la seconda passata si occupa di ordinare soltanto di quest'ultima, si vede che per fare la prima passata bisogna considerare via via gli elementi in giallo con il corrispondente elemento che lo precede, sono queste coppie di valori che vengono confrontate ed eventualmente scambiate fra loro.
[[File:Bubblesort2.png|Bubblesort 2^ passata]]<br />
Riga 59:
}
cout<<endl;
//Bubblesort
for (i=1;i<n;i++)
for ( j= n-1;j>=i;j--)
Line 78 ⟶ 80:
}
</source>
L'efficienza di un algortimo viene espressa con l'ordine di complessita', generalmente esso dipende dal numero n di elementi del vettore, se le perazioni da fare per completare l'algoritmo fossero proporzionali al numero di elementi del vettore l'odine di complessità sarebbe indicato come <math> O(n)</math> e si legge O grande di n. Nel caso del bubblesort le cose vanno peggio di O(n) e i calcoli da farsi sono proporzionalia a <math>n^2</math> secondo un fattore di proporzionalita' di 0.5 si ha allora <math>O(\frac{n^{2}}{2}) </math>. Per il quicksort l'ordine di complessita' e' del <math>O(n\log_{2}n) </math> , meglio del bubblesort ma peggio di un andamento solamente proporzionale ad n . Vediamo in un grafico l'andamento delle istruzioni da effettuare in 3 casi diversi di complessita'
{{Avanzamento|100%|4 dicembre 2014}}
| |||