© 1999-2003, Flemming Koch Jensen
Alle rettigheder forbeholdt
Sortering

Opgaver

"..."

- ...

 

Sortering er algoritmernes legeplads for "George Gearløs"-programmører. Man prøver hele tiden at finde hurtigere sorterings-algoritmer, og emnet er derfor meget stort. Vi skal i det følgende studere en række af de klassiske algoritmer.

 

Vi vil indskrænke os til at sortere arrays, som i alle tilfælde vil være definerede ved:

int tabel[] = new int[N];

hvor N er antallet af elementer vi ønsker at sortere og N>1.

Ikke aftagende orden

Vi vil sortere arrays i ikke aftagende orden. Grunden til at vi ikke kalder det stigende orden er forekomsten af dubletter. Vi vil acceptere dubletter, men hvis vi betegnede det som stigende orden ville det indikere at vi ikke ville have dubletter.

F.eks. er følgende array sorteret i ikke aftagende orden, men ikke i stigende orden, da der ikke er nogen stigning fra 5 til 5.

Figur 1:
Ikke aftagende orden

 

1. Bucketsort

Bucketsort er den hurtigste sorteringsalgoritme der findes. Hvorfor er det så ikke den eneste man bruger? Svaret er, at bucketsort har kraftige bivirkninger, og stiller specielle krav. Vi vender tilbage til problemerne med bucketsort, men først vil vi se algoritmen.

Lad der være givet ovenstående array tabel, og lad værdierne i dette array tilhøre intervallet [0:M-1], dvs. M mulige værdier. Vi vil anvende et hjælpe-array med netop M indgange:

int bucket[] = new int[M];

Vi initialiserer alle indgangene i arrayet til 0. Vi vil for hvert muligt index, i bucket, registrere hvor mange gange det forekommer som værdi i tabel. Det gøres ved at gennemløbe tabel én gang, altså en tidskompleksitet på O(N).

Dernæst gennemløbes bucket og for hver forekomst registreres index som værdi i tabel, som derved overskrives. Det sidste har en tidskompleksitet på O(N+M), derfor samlet O(N) da M ofte kan fastlægges som proportional med N.

Lad os se et eksempel:
Figur 2:
Eksempel med bucketsort
Øverst har vi tabel. I midten laver vi bucket med 10 indgange, da værdierne i tabel alle ligger i intervallet [0:9]. Først laver vi en statistik i bucket over antal forekomster af de forskellige værdier, idet værdierne i tabel afbildes over i index i bucket.
Ud fra statistikken i bucket kan vi "hælde" værdierne tilbage i tabel, idet vi overskriver de oprindelige værdier med de værdier vi har registreret i bucket.
Sammenhængen mellem registreringen i bucket og værdierne i det sorterede array, er i figuren illustreret med pile for udvalgte værdier: 1, 6 og 9.

Algoritmen kan implementeres ved:

Source 1:
Bucketsort
void bucketSort( int[] tabel ) {
  int bucket[] = new int[M];
  
  // array'et initialiseres til 0 (dog ikke nødvendigt i Java)
  for ( int i=0; i<bucket.length; i++ )
    bucket[i] = 0;
  
  // elementerne lægges i spandene
  for ( int i=0; i<tabel.length; i++ )
    bucket[ tabel[i] ]++;

  // elementerne føres tilbage til det oprindelige array
  int pos=0;
  for ( int i=0; i<bucket.length; i++ )
    while ( bucket[i] > 0 ) {
      tabel[pos] = i;
      bucket[i]--;
      pos++;
    }
}

Som nævnt har bucketsort visse vanskeligheder.

M skal helst ikke være for stor. Dvs. værdierne i tabel må ikke være for spredte, da det vil kræve et meget stort hjælpe-array.

F.eks. vil bucketsort være håbløs til at sortere CPR-numre, da det ville kræve et hjælpe-array med ca. 10 milliarder indgange. Hvis vi antager at hvert CPR-nummer kun forekom én gang i vores array vil vi kunne nøjes med et boolean hjælpe-array og dermed et array på ca. 1 GB.

Bucketsort kommer bedst til sin ret hvis M er lille og der er mange dubletter.

 

2. Abstrakt beskrivelse af sortering

Lad der være givet en multimængde M. Til ethvert element i M knytter vi en unik placering tilhørende Z. Vi ønsker nu at ændre placeringen af de enkelte elementer så deres indbyrdes placering overholder en given ordning.
En ordningen definerer relationen < for alle elementpar tilhørende M.
En algoritme der sorterer M, kan evt. opdele M i to delmængder: "Den sorterede del" og "den usorterede del". Som udgangspunkt vil den sortede del være den tomme mængde og den usorterede del hele M. Det er algoritmens opgave at udvide den sortede del, så den til sidst udgør hele M.
Figur 3:
Sorterede delmængde udvider sig
Ikke alle algoritmer har dette inkrementerende forløb, f.eks. ikke bucketsort, men de fleste andre bygger på dette perspektiv.

 

3. Diagrammer

I dette kapitel er der anvendt en række forskellige diagramtyper som det er væsentligt at forstå, for at få det fulde udbytte.

 

3.1 Sorterings-diagrammer

I det følgende skal vi se flere sorteringsalgoritmer der gradvist sorterer et array af integers. For at få et indtryk af hvordan sorteringen udvikler sig vil vi anvende nogle specielle diagrammer [Sedgewick92] (Sedgewick's bog indeholder mange gode diagrammer), som vi vil kalde sorterings-diagrammer. Diagrammerne viser en afbildning af et array, som giver et visuelt indtryk af hvor sorteret det er. Funktionen er ganske enkel:

f(x) = array[x]

Funktionen afbilder index over i elementet.

Hvis vi f.eks. har arrayet:

Figur 4:
Permutation af [0:9]

Vil det blive afbildet som:

Figur 5:
Sorterings-diagram for arrayet

Det giver naturligvis et indtryk af at tallene ikke er sorterede, men vigtigere er billedet når de er sorterede:

Figur 6:
Sorterings-diagram for sorteret array

Den matematisk mindede vil her bemærke identitets-funktionen. Grunden til at vi netop får identitets-funktionen, og dermed en lige linie, skal findes i de tal vi har valgt at sortere. Arrayet indeholder oprindelig en permutation af index-tallene. Når de sorteres opnår man netop identitets-funktionen.

Hvis man sorterer en permutation vil man kunne genkende en sorteret del af et arrayet som en linie med en vis hældning. Da vi arbejder med en permutation af index kan linien aldrig have en hældningskoefficient på mindre end én, men hvis der mangler tal i talrækken vil den være større end én.

Når vi i det følgende bruger disse illustrationer, vil vi anvende et array med 200 tal, da det giver en passende størrelse på diagrammet, når hvert tal repræsenteres med en pixel.

Med disse dimensioner vil et usorteret array f.eks. give følgende diagram:
Figur 7:
Sorterings-diagram for fuldstændig usorteret array med 200 tal
Og et sorteret array vil blive:
Figur 8:
Sorterings-diagram for sorteret array med 200 tal
Man bemærker, at der i det sidste diagram anvendes hvid baggrund. Vi vil, når det er bekvemt, anvende hvid baggrund i de dele af diagrammet der er sorterede. F.eks. i følgende diagram (fra udvalgssortering), hvor den første del af arrayet er sorteret, mens resten stadig er usorteret:
Figur 9:
Sorterings-diagram for delvist sorteret array med 200 tal
At de usorterede danne et kvadrat, fortæller os at de indenfor det pågældende interval er fuldstændig usorterede.

 

3.2 Realtids-diagrammer

Realtids-diagrammer [FKJ] bruges til at illustrere tidsforbrug. I forbindelse med algoritmerne er vi interesseret i at få et indtryk af tidskompleksiteten. Det kan vi gøre ud fra teoretiske betragtninger, men det er også rart at få et konkret indtryk i form at eksperimenter.
For hver algoritme er der derfor lavet et eksperiment, hvor forsøgsresultaterne er afbildet i et diagram1, som f.eks. det følgende fra udvalgssortering:
Figur 10:
Realtids-diagram fra udvalgs-sortering
Vandret er afbildet kardinaliteten af M og lodret tidsforbruget. For at tydeliggøre afvigelserne fra et kontinuert forløb er området under grafen sort.
Ved hjælp af dette realtids-diagram, for udvalgssortering, får vi f.eks. et reelt indtryk af den kvadratiske tidskompleksitet, ved at betragte den parabel-lignende graf.
Alle eksperimenter i dette kapitel er udført på en 200MHz Pentium med JDK 1.2

 

4. Swap

De fleste sorteringsalgoritmer har én operation til fælles. Det skyldes at flertallet af algoritmer arbejder på selve arrayet mens det sorteres, dvs. de flytter ikke elementer over i et andet array (som vi gjorde i bucketsort), men flytter rundt på dem i ét og samme array.

Ombytninger

Det at flytte rundt i det samme array gøres ved ombytninger af to elementer. Denne operation bruges meget, hvorfor vi vil starte med at erklære den som en metode, og antage den erklæret i det følgende.

Metoden kaldes swap og ombytter to elementer, angivet ved deres index.

Source 2:
Swap
void swap( int[] tabel, int x, int y ) {
  int temp = tabel[y];
  tabel[y] = tabel[x];
  tabel[x] = temp;
}

 

5. Udvalgssortering

I udvalgssortering er den sorterede del, den forreste del af arrayet. Idéen i udvalgssortering er at finde det mindste element i den usorterede del af arrayet, og føje det til den sorterede del. I følgende figur er den sorterede del blå, og den endnu ikke sorterede del gullig. Den plads i arrayet, hvor det næste element, fra den usorterede del, der skal føjes til den sorterede del, skal placeres, er markeret med en stærkere gul farve.

Figur 11:
Delvist sorteret array

Som det ses skal det nye element indsættes efter den sorterede del af arrayet. Det skyldes, at der for alle elementer key i den gullige del må gælder, at key>=tabel[i-1], ellers ville et sådant element allerede være udtaget som det daværende mindste, hvilket ikke er sket. Algoritmisk skal man altså finde elementet, og dernæst foretage et swap mellem det og det element der følger efter det sorterede delarray.

Lad os se et eksempel:

Figur 12:
Det usorterede array

Vi skal først have placeret den mindste værdi i arrayet på den første position. Vi finder at 1 er den mindste værdi og swapper 3 og 1:

Figur 13:
swapper 3 og 1

Nu er 1 på plads og vi skal nu finde det mindste element i den usorterede del og swappe det med 9. Den mindste værdi er 3:

Figur 14:
swapper 9 og 3

Igen finder vi den mindste værdi: 4, og swapper den med sig selv. Vi kunne godt lave et check af de enkelte swaps nødvendighed, og i denne situation undgå at swappe, men det vil tidsmæssigt ikke kunne svare sig:

Figur 15:
4 swappes med sig selv

Endelig finder vi at 5 er den mindste værdi i den usorterede del og swapper med 9:

Figur 16:
Det sorterede array

For hvert gennemløb udvides det sorterede delarray med netop ét element, hvorfor tidkompleksiteten for udvalgssortering er O(n2), implementationen bliver nemlig to for-løkker inden i hinanden:

Source 10:
selection-Sort

void selectionSort( int[] tabel ) {

  for ( int i=0; i<tabel.length-1; i++ ) {
    int minIndex = i;

    for ( int candidatIndex=i+1; candidatIndex<tabel.length; candidatIndex++ )
      if ( tabel[candidatIndex] < tabel[minIndex] )
        minIndex = candidatIndex;

    swap( tabel, i, minIndex );
  }
}

Lad os studere udvalgte sorteringsdiagrammer fra en test-kørsel:
Figur 17:
Sorterings-diagrammer for udvalgs-sortering
20 %
40 %
60 %
80 %
Her angiver procenterne, hvor stor en del af arrayet der er sorteret. Man observerer at den usorterede del forbliver fuldstændig usorteret, idet værdierne ligger jævnt fordelt ud over kvadratet.
Et eksperiment med en række testkørsler bekræfter algoritmens kvadratiske tidskompleksitet:
Figur 18:
Realtids-diagram for udvalgs-sortering
Her er grafen yderst til højre oppe på 5,0 sekunder, ved en sortering af 15.000 tal.

 

6. Indsættelsessortering

Indsættelses-sortering arbejder med den samme opdeling af arrayet som fremgår af figur 11. I indsættelsessortering udvider man også den sorterede del med ét element for hver iteration. I stedet for at gennemsøge den usorterede del efter det element, der skal placeres på position i, tager man det element der allerede står der, og indplacerer det i den sorterede del. Dette kræver at der gøres plads til elementet det sted hvor det skal placeres.

Figur 19:
Gør plads til indsættelse af elementet fra position i

Denne plads skabes ved at flytte en del af de sorterede elementer én plads til højre. Dette er muligt, da vi netop fjernede elementet fra position i og dermed levner plads til at elementerne til venstre for position i kan flyttes én til højre.

Flytningen til højre kan kombineres med søgningen  efter det sted hvor elementet skal indsættes ved at swappe det tilbage gennem de sorterede.

Lad os se et eksempel:

Figur 20:
Første element er altid sorteret

Vores udgangspunkt er altid at det sorterede delarray udgøres af det første element.
9 er større end det største element i det sorterede delarray, som altid vil stå længst til højre. Derfor føjes det blot til den sorterede del:
Figur 21:
9 skal ikke flyttes
Her er det næste element: 4, ikke på plads og det swappes med elementet til venstre for det:
Figur 22:
4 swappes på plads
4 er nu større end det største tal i det sorterede delarray til venstre for det, og det føjes til de sorterede:
Figur 23:
1 er den næste der skal på plads
Her er det næste element: 1, ikke på plads og det swappes med elementet til højre. Dette gøres tre gange:
Figur 24:
1 skal swappes tre gange
Efter disse tre swaps er 1 på plads, da det ikke kan komme længere:
Figur 25:
Dernæst skal 5 på plads
Det næste element: 5, skal kun swappes én gang
Figur 26:
5 swappes på plads
før det er større end sin venstre nabo, og dermed på plads:
Figur 27:
Det færdig-sorterede array
Algoritmen kan implementeres med:
Source 11:
insertion-Sort
void insertionSort( int[] tabel ) {

  for ( int i=1; i<tabel.length; i++ ) {
    int runner = i;

    while ( runner>0 && tabel[runner-1]>tabel[runner] ) {
      swap( tabel, runner-1, runner );
      runner--;
    }
  }
}
Da man for hvert element i arrayet indsætter det ved at swappe det tilbage gennem den sorterede del af arrayet, får man en tidskompleksitet på O(n2).
Lad os studere udvalgte sorteringsdiagrammer fra en testkørsel:
Figur 28:
Sorterings-diagrammer for indsættelses-sortering
20 %
40 %
60 %
80 %
Procenterne angiver hvor stor en del af arrayet der er sorteret.
I modsætning til udvalgssortering er hældningskoefficienten for den sorterede del større end en. Det skyldes at den sorterede del nok er sorteret, men ikke sammenhængende. De elementer der mangler i hullerne er spredt ud over den usorterede del af arrayet.
Et eksempel med en række testkørsler bekræfter at indsættelsessoreting har samme tidskompleksitet som udvalgssortering, nemlig kvadratisk.
Figur 29:
Realtids-diagram for indsættelses-sortering
Her er grafen yderst til højre oppe på 3,6 sekunder for en sortering af 15.000 tal, og dermed hurtigere end udvalgssortering.

 

7. Boblesort

Boblesort bygger på idéerne fra udvalgssortering og indsættelsessortering.

Idéen er, at den sorterede del udbygges ved at det næste element sættes på plads på position i - altså idéen fra udvalgssortering, med at placere det rigtige element på positionen med det samme.

Det mindste element swappes ikke direkte på plads, men swappes tilbage gennem den usorterede del - altså idéen fra indsættelsessortering, med at vi rykker de andre så der bliver plads.

Måden hvorpå vi finder det mindste element i den usorterede del er derimod anderledes.

Vi lader os her inspirere af indsættelsessortering, men i stedet for at starte med at swappe fra det mindste element starter vi helt for enden af det usorterede del-array. Vi kommer derfor til at gøre et større arbejde, da vi starter swapningen helt ude for enden, men til gengæld slipper vi for at søge efter det mindste element. Når vi i løbet af vores swapning mod venstre, støder på det mindste element vil det vandre med os hele vejen tilbage til position i. De elementer vi har swappet inden vi nåede det mindste element er ikke spildt arbejde, da de alligevel skal bevæges i den retning de er blevet swappet.

Alt i alt lyder det som en udemærket idé, dog mere kompliceret end udvalgs- og indsættelsessortering.

Navnet boblesort kommer af de mange swaps vi laver. De får det til at "se ud" som om de små elementer "bobler op" igennem arrayet til deres pladser.

Lad os se et eksempel

Figur 30:
Skal placere det rigtige element først 
Vi skal har placeret det rigtige element på den forreste position, og vi gør det ved at boble fra sidste element i arrayet og tilbage mod positionen, altså fire mulige swaps:
Figur 31:
1 swappes tilbage gennem arrayet
Vi ser at de to sidste elementer, i starten, 1 og 5 ikke gav anledning til noget swap, da de er rigtig placeret. Derimod swappes 1 dernæst tre gange og ender på den forreste position.
Dernæst skal vi have placeret det rigtige element på de anden position. Vi starter som altid med at swappe fra enden og tilbage mod positionen, altså tre mulige swaps:
Figur 32:
9 og 4 swappes
Efter swappet med 9 og 4 sker der ikke mere, da 3 og 4 er rigtigt placeret i forhold til hinanden.
Vi starter igen fra enden og vil nu have det rigtige element på den tredie position. Denne gang to mulige swaps:
Figur 33:
9 og 5 swappes
Med swappet mellem 9 og 5 er vi færdige, idet de to sidste elementer allerede er på plads:
Figur 34:
Det sorterede array
Med et meget lille array som det vi bruger i eksmeplet her, får vi nemt et forkert indtryk af den gavnlige virkning af de ekstra swaps som ikke flytter det mindste element på plads. Det skyldes at et swap med to elementer opererer på hele 40% af det lille array ovenfor.
Lad os derfor se et større array blive sorteret. I følgende figur repræsenterer hver linie en udskrift af arrayet for hver gang vi har placeret et rigitgt element på position i:
Tabel 1:
Sortering af array med 20 tal
10 26 11 28 12 16 23 13 17 25 21 15 18 24 14 19 22 29 20 27
10 11 26 12 28 13 16 23 14 17 25 21 15 18 24 19 20 22 29 27
10 11 12 26 13 28 14 16 23 15 17 25 21 18 19 24 20 22 27 29
10 11 12 13 26 14 28 15 16 23 17 18 25 21 19 20 24 22 27 29
10 11 12 13 14 26 15 28 16 17 23 18 19 25 21 20 22 24 27 29
10 11 12 13 14 15 26 16 28 17 18 23 19 20 25 21 22 24 27 29
10 11 12 13 14 15 16 26 17 28 18 19 23 20 21 25 22 24 27 29
10 11 12 13 14 15 16 17 26 18 28 19 20 23 21 22 25 24 27 29
10 11 12 13 14 15 16 17 18 26 19 28 20 21 23 22 24 25 27 29
10 11 12 13 14 15 16 17 18 19 26 20 28 21 22 23 24 25 27 29
10 11 12 13 14 15 16 17 18 19 20 26 21 28 22 23 24 25 27 29
10 11 12 13 14 15 16 17 18 19 20 21 26 22 28 23 24 25 27 29
10 11 12 13 14 15 16 17 18 19 20 21 22 26 23 28 24 25 27 29
10 11 12 13 14 15 16 17 18 19 20 21 22 23 26 24 28 25 27 29
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 25 28 27 29
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
Med blåt er markeret de elementer der kan garanteres på plads. Som det ses er de to nederste linier ens. Det skyldes at der skal en ekstra iteration til, for at algoritmen kan "se", at arrayet er sorteret. Algoritmen ser dette ved at der i løbet af iterationen ikke forekommer nogen swaps.
Tre af tallene er markeret med fed skrift: 17, 20 og 28. De repræsenterer forskellige "boblinger".
28 starter nede i den forkerte ende og har langt hjem til sin plads. Da den er større end alle de elementer den møder (indtil den når 29) vandrer den stødt og roligt "mod strømmen", ét skridt for hver iteration.
17 gennemgår en zigzag-kurs, da den både møder elementer, der er større og mindre end den selv.
20 starter i den høje ende og skal ind til midten hvor den hører hjemme. To gange rykker den mere end én position pr. iteration. Første gang hvor den er mindre end både 22 og 29, og anden gang hvor den er mindre end 25 og 21.
Man får her et bedre indtryk af at ikke alle elementer bliver flyttet lige hensigtsmæssigt. F.eks. starter 17 lige ved siden af dens endelige position, men vandrer en del rundt før den finder på plads.
Algoritmen kan implementeres med:
Source 12:
bobleSort
void bobleSort( int[] tabel ) {

  for ( int i=0; i<tabel.length; i++ ) {
    int swaps = 0;

    for ( int p=tabel.length-1; i<p; p-- )
      if ( tabel[p-1] > tabel[p] ) {
        swap( tabel, p-1, p );
        swaps++;
      }

    // hvis vi ikke ændrede noget denne gang, kommer
    // vi heller ikke til at gøre det næste gang
    if ( swaps == 0 )
      break;
  }
}
Med de to løkker bliver tidskompleksiteten O(n2).
Lad os studere udvalgte sorteringsdiagrammer fra en testkørsel:
Figur 35:
Sorterings-diagrammer for boblesort 

20 %
40 %
60 %
80 %

Procenterne angiver hvor stor en del af arrayet, der er sorteret.
Som udgangspunkt kan man observere at de usorterede ikke vedbliver med at være fuldstændig usorterede, men at der er en tendens i retning af sorterethed.
Man ser nemlig at grafen generelt har følgende udseende:
Figur 36:
Generelt billede af et sorterings-diagram for boblesort
Buen fremkommer ved at elementerne bliver flyttet med tilbage mod deres rigitge position af de ekstra swaps der kommer før vi støder på det mindste element i den usorterede del.
Den anden vej er der ingen bue. Det skyldes at elementerne kun kan vandre én position til højre pr. iteration. Derfor vandrer "skyen" af elementer ét skridt mod højre pr. iteration. Et fænomen man kan se hvis man sammenligner sorteringsdiagrammerne.
Et eksperiment med en række testkørsler bekræfter at boblesort har kvadratisk tidskompleksitet:
Figur 37:
Realtids-diagram for boblesort
Her er grafen yderst til højre oppe på 3,3 sekunder for kun 10.000 elementer. Det bekræfter at boblesort er en meget ringe sorteringsalgoritme; hvilket er almindelig kendt. Boblesort er dog algoritmisk interessant; hvilket berettiger dens tilstedeværelse her.

 

8. Quicksort

I praksis en hurtig algoritme

I modsætning til de tidligere algoritmers navne, fortæller navnet Quicksort [Hoare 62] ikke mere om den, end betegnelser som "Ultra Super de Luxe". Hvis man ser på tidskompleksiteten, i worst case, er den kun O(n2). Det der gør den attraktiv, er derimod den gennemsnitlige tidskompleksitet på O(n log n), og at den i praksis ofte er hurtigere end andre O(n log n) algoritmer Et andet træk ved den er, at den i forhold til algoritmer med worst case O(n log n) er uhyre simpel.

Lad os se den grundlæggende struktur i algoritmen:

Source 13:
bobleSort med kald af partition

void quickSort( int[] tabel, int left, int right ) {
  if ( left < right ) {
    int midt = partition( tabel, left, right );
    quicksort( tabel, left, midt-1 );
    quicksort( tabel, midt+1, right );
  }
}

De tre parametre der gives til quickSort angiver en del af et array:

Figur 38:
Angivelse af delarray

Stykket der indikeres ved left og right er med hele det gullige (og den blå), altså begge inklusiv.

quickSort sortere elementerne i det gullige område. Den gør det ved her at finde et element, der ved sin placering deler det hele i to. Dette element deler de andre på en sådan måde, at elemeneterne til venstre for det, er mindre end eller lig det, og alle elementer til højre for det, er større end eller lig det. De ville dermed være en anelse sorterede!

Nu er sandsynligheden for, at der findes et sådant element i den gullige usorterede del ikke stor. Man er derfor nød til at ændre på rækkefølgen af elementerne så det bliver tilfældet. Det er det, der er partitions opgave.

partition løser den ved ganske enkelt at fastslå at elementet længst til højre, tabel[right], skal være dette dele-element. Nu kan man naturligvis ikke regne med at alle andre elementer skulle være mindre end tabel[right], men så må man flytte tabel[right], på et tidspunkt. Efter at have registreret værdien af tabel[right] begynder delalgoritmen at flytte rundt på de andre elementer. Det gøres ved at arbejde med to index l og r, der starter i hver deres ende af det usorterede område. De arbejder sig nu ind mod "midten", hvor det er vores hensigt at placere tabel[right] til slut. For at det skal komme til at passe til sidst bliver tabel[l] og tabel[r] sammenlignet for hver gang en af dem rykkes, og hvis de begge er placeret forkert, dvs. tabel[l]>tabel[r] laves der et swap, hvorefter de er placeret rigtigt ifht. "midten". Hvis kun den ene er placeret forkert, flyttes den anden. Når de til slut krydser hinanden, laves der et swap mellem tabel[right] og det sidste element der var større end tabel[right], nemlig "midten". Herefter har partition løst sin opgave.

Lad os se et eksempel, der illustrerer teknikken. I figurene er det udvalgte "midt"-element blåt, fordi det i løbet af eksemplet ende med at være på plads. De endnu ikke sorterede elementer er gullige, og dem vi i denne omgang er færdige med at bearbejde er med en stærkere gul farve.

Bemærk at vi vælger det sidste element i delarrayet som vores "midt"-element, men venter med at placere det, da vi ikke ved hvor det skal være. En ting ved vi dog: Værdien af "midt"-elementet er 5; hvilket vi sammenligner de andre med.

Figur 39:
Swap af 9 og 4 over midten

Her swapper vi 9 og 4 hen over midten, da 4 er mindre end 5 og 9 er større end 5. 5 skal senere placeres et eller andet sted mellem 9 og 4, og med den rækkefølge de har nu bryder de ordningen i forhold til 5. Derfor skal de swappes.

Efter de er swappet kan 5 placeres et sted mellem dem og de tre elementer vi isoleret set var sorterede i forhold til hinanden.

Dernæst kan vi flytte mod midten fra begge sider, da 3 og 8 er i rigtig rækkefølge i forhold til en placering af 5 imellem dem:
Figur 40:
Swap af 8 og 4 over midten
Vi støder på 8 og 4, der begge er placeret forkert i forhold til 5. Derfor swappes de.
Efter dette swap kan vi bevæge os mod midten fra begge sider, og specielt langt for venstre sides vedkommende:
Figur 41:
Swap af 7 og 5 placerer 5 i midten
De to sider støder nu sammen og vi swapper med det elementet til højre for denne midterlinie; hvorved 5 kommer på plads, og 7 er rigtig placeret i forhold til 5.
Man ser nu at alle elementer til højre for 5 er større end eller lig 5, og tilsvarende er alle elementer til venstre for 5 mindre end eller lig med 5.
Dette var partitions-delen af quicksort. Vi vender nu tilbage til resten af algoritmen.

Som det ses af de to efterfølgende kald af quickSort, er quickSort rekursiv. Den generelle idé med rekursion, er at løse en (lille) del af et problem, og sende resten videre; hvor resten vel at mærke er samme slags problem som det oprindelige. Hvad er den løste del efter partition? Eftersom alle elementer til venstre for tabel[l] er mindre end eller lig den, og analogt større til højre for, er tabel[l] placeret rigtig, og skal aldrig flyttes igen! Det er måske overraskende, at den del af problemet quickSort vælger at løse hedder: "Placer et mere eller mindre tilfældigt element på sin endelige plads". Samtidig med at dette lille delproblem løses, ser man at resten herefter er tættere på at være løst, idet højre og venstre delarray er sorteret i forhold til hinanden. Rekursionen i quickSort løser dermed ikke ét lille delproblem, men snarere "1½".

Ved de efterfølgende kald af quickSort sorterer man naturligvis de to resterende delarrays. Da partition ikke fylder mere end nogle få linier vælger man ikke at lave den til et metodekald, men skriver den direkte ind i quickSort. Vores endelige algoritme bliver dermed:

Source 14:
quickSort
void quickSort( int[] tabel, int left, int right ) {
  if ( left < right ) {
    int midValue = tabel[right];
    int l = left;
    int r = right-1;

    while ( l<=r ) {
      while ( l<=r && midValue<=tabel[r] )
        r--;
      while ( l<=r && tabel[l]<midValue )
        l++;
      if ( l<r ) {
        swap( tabel, l, r );
        r--;
        l++;
      }
    }

    swap( tabel, l, right );

    quickSort( tabel, left, l-1 );
    quickSort( tabel, l+1, right );
  }
}

void quickSort( int[] tabel ) {
  quickSort( tabel, 0, tabel.length-1 );
}
Lad os studere udvalgte sorteringsdiagrammer fra en testkørsel:
Figur 42:
sorterings-diagrammer for quicksort
10 %
25 %
50 %
75 %

Procenterne angiver hvor stor en del af det samlede antal rekursive kald der er foretaget.

Man ser at arrayet hele tiden består af en række usorterede delarrays (kvadraterne), med mellemliggende elementer der er på plads (de punkter hvor kvadraterne mødes). Da kvadraterne ikke er sammenfaldende, hvis de projeceres ind på anden-aksen, ser man ligeldes den delvise sortering hvor elementerne i hvert delarray er placeret i det rigtige index-interval, men ikke på den rette position i det.

Lad os se et realtids-diagram fra en række testkørsler:

Figur 43:
Realtids-diagram for quicksort

Yderst til højre sorteres der 200.000 tal på 0.33 sekunder. Det er 20 gange så mange tal som boblesort på en tiendedel af den tid, den er om at sortere 10.000 tal.

Det viser at man vinder meget ved at vælge en O(n log n), selv om de er mere komplicerede end O(n2) algoritmerne.

 

9. Mergesort

Mergesort, eller flette-sortering, bygger på en grundlæggende teknik, der hedder fletning.

 

9.1 Fletning

Vi vil se på fletning af arrays eller delarrays. Lad os se et eksempel på to arrays der flettes over i et andet array.

De to arrays:

Figur 44:
De to arrays der skal flettes

Det resulterende flettede array:

Figur 45:
Det flettede array

Man observerer at de to arrays som udgangspunkt var sorterede, og at det flettede array ligeledes er sorteret. Ordet fletning kommer bedst til sin ret hvis vi tegner resultatet med to "tråde", der går gennem elementerne, efter hvilket array de kom fra.

Figur 46:
Fletningens sammenhæng

Algortimisk er en fletning, et gennemløb af de to arrays. Man ser hele tiden på det "forreste" element i de to arrays, og en sammenligning er afgørende for, hvilken der skal over i resultat-arrayet. Man bliver ved på denne måde indtil begge arrays er "tømt" for elementer.

Den version af fletning vi skal bruge, arbejder ud fraat de to arrays, der skal flettes, ligger i forlængelse af hinanden i et større array. Resultatet skal placeres oven i de positioner de to arrays pt. ligger i.

Det er meget kompliceret at foretage fletningen uden et hjælpe-array. Vi vil derfor bruge et sådant. Vi vil kopiere de to delarrays over i et hjælpearray af samme længde som det store array de kommer fra, på de samme positioner, og dernæst flette fra det, tilbage i det gamle (Det kan måske undre, at vi er villige til at allokere et hjælpearray, der kan være betydelig større end nødvendigt, eftersom et hjælpearray med samme længde som de to delarrays tilsammen er tilstrækkeligt. Vi skal senere se hvorfor det er en god idé).

Figur 47:
Fletning til mergesort

Vi vil i vores algoritme bruge left, som index for elementet længst til venstre i delarray nr. 1, og right, som index for elementet længst til højre i delarray nr. 2. Endelig vil vi bruge middle til at betegne index for elementet længst til højre i delarray nr. 1, og dermed skellet mellem delarray nr 1 og 2.

Hvorfor skal delarray nr. 2 vendes om? Idéen er at løse et problem, der opstår når det ene delarray er løbet tomt, mens der stadig er flere i det andet; uden at skulle lave speciel kode til situationen. Når vi vender det andet delarrays om, vender de største værdier ind mod hinanden. Når det ene løber tomt, kommer dets index til at pege på det største element i det andet delarray, og den vil derfor ikke flytte sig mere. Samtidig betyder det, at det andet delarray tømmes ved sammenligning med dette største element.

Vi skal derfor kopiere delarray nr. 2 over omvendt og sætte vores hjælpe-index r i dette delarray til right.

Lad os se et eksempel.
Vi har følgende to del-arrays i et stort array: tabel.
Figur 48:
Del-arrays af tabel
Vi kopierer nu de to del-arrays over i et hjælpe-array help, med samme størrelse som tabel. Ved at hjælpearrayet har samme størrelse som det oprindelige array, opnår vi at de samme index kan anvendes; hvilket simplificerer index-kalkulationerne.
Figur 49:
Del-array kopieret over i help
Elementerne skal nu flettes tilbage i det oprindelige array, idet vi overskriver de gamle værdier dér. help[r] er mindre end help[l] og vi flytter help[r] tilbage i tabel, som det første element og rykker r én mod midten:
Figur 50:
Det første element flyttet fra help til tabel
Vi bliver nu ved med at sammenligne help[l] og help[r], idet vi altid flytter det mindste af de to elementer tilbage til tabel og flytter l eller r. Hvis de to elementer er ens vælger vi en vilkårlig af dem.
Når der kun mangler to elementer er billedet:
Figur 51:
Med to elementer tilbage
Vi har netop valgt at flytte 8'eren fra den venstre halvdel på plads og l er flyttet én til højre så den står på 9'eren.
Det næste element vi flytter er 8'eren, da help[r] er mindre end help[l]. Derved kommer l og r til at referere til det samme element, der er det sidste.
Figur 52:
l og r på samme element
Sidste gang vælger vi en vilkårlig af help[l] og help[r], da de har samme værdi.
Efter vi har valgt, flytter vi enten l eller r, og for første gang er r nu mindre end l.
Vi kunne derfor vælge l<=r som vores kørselsbetingelse, men da vi alligevel skal bruge en index-variabel til tabel (for at kunne flytte værdierne tilbage) vælger vi i stedet at bruge den i forbindelse med en for-løkke.
Vores implementation, af fletningen, bliver derfor:

int l, r;

for ( l=left; l<=middle; l++ )
  help[l] = tabel[l];
for ( r=middle+1; r<=right; r++ )
  help[ right - ( r - middle ) + 1 ] = tabel[r];
l = left;
r = right;

for ( int res=left; res<=right; res++ )
  if ( help[l] < help[r] ) {
    tabel[res] = help[l];
    l++;
  } else {
    tabel[res] = help[r];
    r--;
  }

 

9.2 Sortering med fletning

Med ovenstående fletnings-algoritme kan man fra to sorterede del-arrays komme til et samlet sorteret del-array for dem begge. Vi kan bruge dette til at lave en rekursiv sortering, analog til quicksort. Idéen vil her være rekursivt at dele arrayet op i del-arrays ned til ét element og så flette tilbage, større og større delarrays, indtil hele arrayet er sorteret. Vi vælger derfor ved hvert rekursivt skridt at dele arrayet op i to lige store dele, kalde rekursivt for at få de to dele sorteret, og endelig selv flette de to delarrays. Vores endelige implementation bliver:

int[] help = new int[tabel.length];

void mergeSort( int[] tabel, int left, int right ) {
  int l, r;

  if ( left < right ) {
    int middle = ( left + right )/2;
    mergeSort( tabel, left, middle );
    mergeSort( tabel, middle+1, right );

    for ( l=left; l<=middle; l++ )
      help[l] = tabel[l];
    for ( r=middle+1; r<=right; r++ )
      help[ right - ( r - middle ) + 1 ] = tabel[r];
    l = left;
    r = right;

    for ( int res=left; res<=right; res++ )
      if ( help[l] < help[r] ) {
        tabel[res] = help[l];
        l++;
      } else {
        tabel[res] = help[r];
        r--;
      }
  }
}

void mergeSort( int[] tabel ) {
  mergeSort( tabel, 0, tabel.length-1 );
}

Man bemærker at vi har placeret hjælpearrayet globalt i forhold til metoderne (i en konkret implementation vil man naturligvis gøre referencen til en instans-variabel, men vi vil i dette kapitel undlade at se på en objektorienteret implementation). Alle de rekursive "metode-kopier" kan være fælles om dette hjælpearray, da det ikke bruges mellem kald. På den måde blive prisen vi skal betale for hjælpearrayets allokering ikke så stor, og vi kan samtidig anvende de samme index som i de to del-arrays. Derfor er vi ikke så betænkelige ved at have et ekstra array med samme størrelse som det vi sorterer.
Lad os studere udvalgte sorterings-diagrammer fra en testkørsel:
Figur 53:
Sorterings-diagrammer for mergesort
25 %
50 %
51 %
90 %

Procenterne er af det samlede antal rekursive kald. Springet mellem 50% og 51% er 5 kald.

Man observerer en række stejle "linier" ved siden af hinanden. Det skyldes at hver linie repræsenterer et del-array hvori elementerne er sorterede. Efterhånden flettes disse del-arrays og linierne bliver mindre spejle og mere sammenhængende. Man observerer ligeledes, at arrayet overordnet set sorteres fra venstre mod højre. Det skyldes at vi hele tiden foretager et rekusivt kald for at sortere det venstre del-array før det højre (inorder gennemløb af rekursionstræet; hvis man kender disse betegnelser).
Lad os se et realtids-diagram fra en række testkørsler:
Figur 54:
Realtids-diagram for mergesort
Yderst til højre sorteres 200.000 tal på 0,7 sek. Det er ca. dobbelt så lang tid som quicksort er om det samme antal.

Mergesort har i worst case en tidskompleksistet på O(n log n), altså bedre end quicksort. Men som det ses har den ikke quicksorts enkelthed i koden, og er i praksis også langsommere.

 

10. Radix sortering

Radix sortering bygger på en idé der allerede lå til grund for bucketsort. Da radix sortering lettest at forstå med lexikografisk sortering, vil vi først lave en algoritme til sortering af ord, og derefter gå over til det sædvanlige array.

 

10.1 Alfabetisk sortering

Når man skal lave alfabetisk sortering er det en fordel af arbejde med et array af pointere til strenge. På den måde skal man ikke flytte rundt på hele tekststykker, men blot flytte nogle pointere. Vores array bliver derfor:

char **tabel[N];

I radix sortering laver man en grovsortering der gradvist forfines, indtil sorteringen er fuldbyrdet. Vi vil derfor starte med at sortere ordene efter det første bogstav osv. som det er illustreret i figur 21.6.

Figur 21.6 Alfabetisk radix sortering

I figuren er med grå vist den del af ordene der er sorterede. Hvis vi kalder den grå del af et ord for hovetdet, og den lyse del halene, kan man tænke på det at komme fra en delsortering af array&rsquo;et til den næste ved at holde hovederne fast og sortere halerne med de samme hoveder indbyrdes. At dette i praksis gøres ved at flytte hele ord rundt betyder ikke noget, blot man ikke blander ord med ens hoveder sammen.

Det ses også af figuren, at array&rsquo;et efter et skridt er næsten sorteret. Det skyldes ikke radix sorteringen. Det er en konsekvens af, at antallet af bogstaver i alfabetet ikke er meget mindre end antal ord i array&rsquo;et. Hvis array&rsquo;et f.eks. havde været på 10.000 ord skulle man længere hen i sorteringen før den knækkede. Det vil nemlig ske når delarray&rsquo;ene med de samme hoveder er arbejdet ned til en størrelse i nærheden af antallet af forskellige forbogstaver i halerne.

Det spørgsmål der aægoritmisk står tilbage er hvordan man skal foretage skridtet fra en delsortering til den næste, hvilken form for sortering kan man bruge. Svaret er naturligvis, at man kan bruge en hvilken som helst. Da vi kun er interesseret i at illustrere selv radix sorteringen og i næste række brugen af et array til strenge, vil vi blot bruge en simpel, nemlig udvalgssortering. I så fald kunne algoritmen implemeneteres i C++ ved:

void sub_sort(char **tabel[], int pos) {
}

void sort(char **tabel[]) {
}

 

10.2 Radix exchange sortering

 

10.3 Straight radix sortering

fodnoter:

 

1

I forbindelse med realtids-diagrammerne er der foretaget retouchering.

Det skyldes i første række, at alle diagrammerne har en lille forstyrrelse i starten af forløbet. Hvad den skyldes ved jeg ikke, men det kan evt. være JVM der holder en pause, hvor den ordner "et eller andet" - f.eks. initialiserer garbage collectoren.

Realtids-diagrammerne for udvalgs- og indsættelsessortering er ikke retoucherede, da forstyrrelsen ikke er så markant. I følgende figur, fra udvalgssortering, er forstyrrelsen markeret.
I forbindelse med quicksort er der foretaget en yderligere retouchering. I eksperimenterne der ligger til grund for realtids-diagrammerne er anvendt System.currentTimeMillis(), der returnerer en angivelse i ms. Der er dog det problem, at den for det meste sætter tusindedelene til 0, og i realiteten kun kan bruges ned til hundrededele sekunder. Quciksort er for hurtig til at det giver et præcist billede. Hvis man ikke retoucherer realtids-diagrammet får det følgende udseende (her vist fra et andet eksperiment):
Retoucheringen er lavet ved at tilføje støj i form af en tilfældigt ekstra decimal på tusindedelenes plads. Hvis man ved hvad man leder efter, kan man stadig ane trappeformen i det retoucherede diagram.
Alle retoucheringer er foretaget af pædagogiske grunde, da disse "virkeligheds-fænomener" vil aflede opmærksomheden fra det væsentlige, nemlig tidskompleksisteten.