Eksempel: Bubble sort

Forrige side: Index out of bounds -- Tastaturgenvej: 'p'

Næste side: Brug af qsort fra standard biblioteket -- Tastaturgenvej: 'n'

Arrays og Pointere - slide 18 : 30

Eksempel: Bubble sort

Bubble sort er en klassisk, men ikke særlig effektiv sorteringsalgoritme

void bubble(int a[] , int n){      /* n is the size of a[] */ 
   int   i, j;

   for (i = 0; i < n - 1; ++i){
     for (j = n - 1; j > i; --j)
       if (a[j-1] > a[j])          /* Comparison           */
          swap(&a[j-1], &a[j]);    /* Exchange             */
   }
}

Hele 'bubble sort' programmet - med løbende udskrift af arrayet.

Output fra bubble sort programmet.

Illustration af de forskellige faser i boblesorteringen

Det er let at set at boblesorteringsprogrammet foretager i størrelsesordenen n² sammenligninger og ombytninger.

De gode sorteringsalgoritmer kan nøjes med i størrelsesordenen n log(n) sammenligninger og ombytninger.