Eksempel: Bubble sort

Forrige side: Pointers og arrays (3) -- Tastaturgenvej: 'p'

Næste side: Pointeraritmetik -- Tastaturgenvej: 'n'

Pointers og Arrays - slide 17 : 26

Eksempel: Bubble sort

Boblesortering 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])
          swap(&a[j-1], &a[j]);
   }
}

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

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.