PDA

Visualizza la versione completa : complessitÓ computazionale bubble sort


SSSS90
26-06-2014, 14:43
Salve ho il seguente algoritmo di bubble sort,non riesco a capire perchŔ l'algoritmo ha una complessitÓ computazionale di n^2,supponendo di partire da un vettore controordinato 7 5 2 possiamo dire che vengono fatti n=3 confronti per il ciclo while e poi..?bisogna tenere conto anche di tutte le volte che viene richiamato il for e l'if per valutare la complessitÓ computazionale:confused:?




v o i d bubblesort ( i n t v [] , i n t n ){
2: i n t i ,j , tmp ;
3: i n t flag_swap ;
4:
5: i =0;
6: flag_swap =1;
7: w h i l e ( ( flag_swap == 1) && (i <n -1) ) {
8: flag_swap =0;
9: f o r (j =0; j <n -1 - i ;j ++){
10: i f (v[ j] > v[ j +1]){
11: flag_swap =1;
12: tmp = v[j ];
13: v[j ]= v[j +1];
14: v[j +1]= tmp ;
15: };
16: }
17: i= i +1;
18: }
19: }

Loading