Udførselstid for bubblesort

Denne artikel er den første i en række af artikler om sorterings og søgnings-algoritmer. I første omgang vil jeg give en intro til begrebet udførselstider, samt beregne udførselstiden for bubblesort-algoritmen.

Denne artikel og de kommende er nok ikke for begyndere, men de lidt mere øvede kan få noget ud af dem. Det gør det selvfølglig nemmere hvis man har haft matematik på gymnasie-niveau. Kommentér endelig hvis der er noget der er svært at forstå eller fremstår uklart, så skal jeg nok uddybe i en kommentar.

Til tider laver man applikationer som på visse steder kræver meget stor hastighed. For at kunne sammenligne og udvælge algoritmer, er det i disse situationer nødvendigt at kunne lave et overslag over udførselstiden for algoritmerne.
F.eks. kan kan man se på nedenstående to for-løkker:

for (int i = 0; i<n; i++) {
   
   for (int j 0 0; j<n; j++) {
      Q++;
   }

}

Begge løkkerne løber fra 0 til n. For hvert gennemløb af den yderste løkke, skal den inderste løkke igennem n gennemløb. Det betyder at det samlede antal gennemløb er n*n = n^2. Hvis vi betragter indmaden Q++; som tagende konstant tid (den er uafhængig af n), siger vi at udførselstiden for de to for-løkker er O(n), som vi udtaler 'Store-O af n'. Tilsvarende siger vi at når noget tager konstant tid, er
udførselstiden O(1).
For de mere matematiske er definitionen på O følgende:
Lad f(n) og g(n) være funtioner som tager positive heltal som input, og giver reelle tal som output (f, g: N -> R).
Hvis der findes en reel konstant c > 0, og et naturligt tal N >= 1 sådan at f(n) <= c*g(n) for ethvert naturligt tal n>N, er f(n) begrænset af g(n) og vi skriver f(n) er store O af g(n).
F.eks. gælder n er O(n^2) og log(n) er O(n).

Inden jeg går igang med bubblesort-algoritmen, giver jeg lige et lille bevis først.
Lad SUM(i=1, n, f(i)) betegne summen f(1)+f(2)+...+f(n). Normalt ville jeg bruge et sumtegn, men det ved jeg ikke lige hvordan jeg laver her.
Vi vil vise at

SUM(i=1, n, i) = n*(n+1)/2.

Hvis n=1, gælder det i hvert fald da

1*(1+1)/2 = 1*2/2 = 1.

Vi skal nu vise at det gælder for n>=2.
Antag at det gælder for alle n´ Fra antagelsen har vi

SUM(i=1, n, i) = n + (n-1)n/2 = 2n^2 + n^2 - n/2 = (n^2 +n)/2= n(n+1)/2

Og beviset er færdigt.

Lad os nu tage fat på bubble-sort. Først lidt om hvordan den fungerer.
Vi ønsker at sortere en følge af elementer, hvor alle elementer kan semmenlignes indbyrdes. Det kan f.eks. være en tal-følge.
bubble-sort algoritmen løser denne opgave ved at foretage en række gennemløb af følgen. Under hvert gennemløb sammenligner den et element med naboen. Hvis naboen er mindre byttes om på elementerne. Følgen sorteres ved at udføre n, sådanne gennemløb, hvor n er antallet af elementer.
I første gennemløb, når det største element er bliver fundet, vil det blive flyttet hele vejen til enden af følgen, idet alle de andre elementer er mindre.
I andet gennemløb, vil det næst-største element flyttes til den anden-sidste position i følgen.
Ved slutningen af det i'te gennemløb vil de n-i elementer længste til højre være i en endelig position. Dvs., det er altså korrekt at begrænse antallet af gennemløb til n, ydermere tillader det at det i'te gennemløb begrænses til de første n-i+1 elementer.
Dvs., udførselstiden for et enkelt gennemløb er O(n-i+1), og den samlede udførselstid for algortimen er så O(SUM(i=1, n, n-i+1)).
Hvis vi skriver denne sum ud, får vi

O(n + (n - 1) + ... + 2 + 1) = O(SUM(i=1, n, i).

Men denne sum fandt vi jo før til at være n*(n+1)/2, som er O(n^2).
Dvs., udførselstiden for bubblesort algoritmen er O(n^2).
Vi siger også at algoritmen tager kvadratisk tid.
Jeg giver lige et hurtigt eksempel på bubblesort med lidt pseudo-kode. Den kan hurtigt skrives om til læserens yndlings sprog.

bubbleSort(int[] a) {
 int n = a.length();
 for (int i=0; i<n; i++)
   for (int j=0; j<n-i; j++)
    if a[j] >a[j+1] swap(a[i], a[j])	
}

bubble-sort algoritmen er i mange tilfælde alt for langsom. Der findes dog gudskelov andre alogritmer, som merge-sort og quicksort som kører meget hurtigere.
Nemlig O(n*log(n)), men det gemmer jeg til en anden artikel.
Sig til hvis artiklen var alt for svær. Stoffet er nemlig ikke nemt, og hvis der ikke er nogen der synes det er bare en lille smule spændende, så kan jeg godt bruge min tid på noget andet :)