Tags:    delphi

Indhold:

- Sorteringsalgoritmer i Delphi
- Bubble-Up
- Minimumsort
- Insertionsort
- Shellsort
- Quicksort
- Sorteringstider
- Andre algoritmer

Sorteringsalgoritmer i Delphi

Sortering af data er en af computerens vigtigste opgaver, især indenfor professionel edb. Nogle dataloger påstår at sortering udgør 30-50 % af en professionel servers arbejde. Nu er der sikkert ikke mange af jer der programmerer server-applications, og Delphi kommer da også i forvejen med et par sorteringsfunktioner, de opfylder bare ikke i det mindste de krav man har hvis man arbejder med større mængder af tal eller strings. Med den rigtige algoritme er der desuden en masse tid at spare!
En algoritme beskriver en regnemåde. Sådan en kan være ret kompliceret, derfor starter vi med noget nemt. Allerførst skal vi have noget udgangsmateriale!

Lad os definere et array med 10000 integer-felter. Da det her hovedsageligt er teori ka' du selv om hvor du vil definere henne.

var
talarray: array[1..10000] of integer; //array som senere skal sorteres

Ok, lad os begynde med at fylde arrayen med vilkårlige, usorterede tal:

for i := 1 to 10000 do
  talarray[i ] := random(99999999);

Nu mangler vi bare en algoritme til at sortere de tal der ligger inde i arrayen. Der er som sagt forskellige. Vi begynder med noget nemt:

Bubble-Up

Bubble-up metoden fungerer på den måde at den går gennem arrayen flere gange og sammenligner hvert tal med det næste. Hvis de står i forkert rækkefølge byttes de om. Efter at algortimen har gennemgået array tilstrækkelig mange gange er alle tal sorteret! I værste tilfælde skal et tal dog "bubble" sig hele vejen gennem arrayen.

procedure Bubble_up;
var 
  h, tempint: integer; 
  bubble: boolean; 
begin
  repeat
    bubble := false;	//forløbig kun en påstand 
    for h := 1 to 10000 - 1 do
      if talarray[h] > talarray[h+1] then begin 
        tempint := talarray[h];		// 
        talarray[h] := talarray[h+1];	// trekantsbyt
        talarray[h+1] := tempint;		//
        bubble := true;
      end;
  until bubble = false;
end;

Som øverste struktur anvender vi en repeatlykke, fordi den netop opfylder hvores krav. Den går gennem arrayen mindst én gang, og den kan afbrydes på ethvert tidspunkt, nemlig når sorteringen er færdig hvilket vi ikke ved er hvornår.
Det første vi så gør er at påstå at arrayen ér sorteret, (bubble := false). Så kører vi gennem den med en for-lykke og tjekker for hvert tal om det er større end det næste. Er det det så udbyttes de to hva. et trekantsbyt, som vi skal bruge en hjælpevariable til (tempint). Forlykken skal ikke gå til 10000 fordi så ville den prøve at sammenligne med talarray[10001] hvilken ikke findes. Sker der byt, så trække vi endvidere vores udsagn om en færdig sorteret array tilbage, idet vi siger at bubble := true.
På et tidspunkt vil if-sætningens forudsætning aldrig være opfyldt, og repeat-lykken afbrydes. Arrayen er sorteret!

På den måde kan du sortere alle mulige lister, arrays, filer osv. Det er også meget nemt, men hvis man har at gøre med mange elementer (10000+) så er bubble-up metoden desværre alt for langsom - den laver alt for mange byt!

Minimumsort

Algoritmen betegnes også for Selection-sort! Minimumsort sorterer næsten som et menneske ville gøre det i de fleste tilfælde. Den antager i første omgang element 1 som det mindste. Så går minimumsort gennem alle følgende elementer og sammenligner med element 1. Hvis den finder et mindre byttes de to i et trekantsbyt. Efter første gennemløb står det mindste element på den måde på plads nr. 1. De samme sker for alle de andre elementer.

procedure Minimumsort;
var 
  h,j,tempint:integer;
begin
  for h := 1 to 10000 - 1 do
    for j := h + 1 to 10000 do
      if talarray[j] < talarray[h] then begin
        tempint := talarray[h];		//
        talarray[h] := talarray[j];		// trekantsbyt
        talarray[h] := tempint;		//
      end;
end;
end;

Til minimumsort skal to for-lykker forgrenes, så at hvert element kan sammenlignes med det andet. Funktionsprincippet er meget simpelt og behøver ikke forklares yderlige, hvis du har forstå bubble-up metoden.
Minimumsort laver også ret mange ombytninger og sammenligninger. Derfor er den også relativ uegnet til rigtig store datamængder. Hvis du bare skal sortere en 1000 elementer, så kan du roligt tage den alligevel. For den er kort og nem at gennemskue.

Insertionsort

Minimumsort har den ulempe at kun naboelementer bliver byttet. Shellsort er en udvidelse af Minimumsort idet den kigger på elementerne et efter et, og indføjer elementet på den rigtige plads blandt de allerede gennemgåede elementer. Det er på samme måde mange kortspillere sorterer deres kort på hånden!

procedure InsertionSort; 
var 
  h,j,temp : integer; 
begin 
  for h := 2 to 10000 do begin 
    temp := talarray[h]; 
    j := h; 
    while (j > 1) and (talarray[j - 1] > temp) do begin 
      talarray[j] := talarray[j-1]; 
      dec(j); 
    end; 
    talarray[j] := temp; 
  end; 
end;

Overordnet er det her en for-lykke som "crawler" gennem arrayet. Variable j og temp fastholder de aktuelle værdier. While-lykken søger for det første for at finde den passende nye plads (her skal der kun søges fra "højre" fordi elementerne her allerede er sorteret) og skubber så de efterliggende elementer én plads til højre for at skaffe plads til det nye! På den måde gennemkøres arrayet principielt kun 1 gang, men dannelsen af frie pladser til indføjelse af det nye element kræver en del energi, hvilket i reglen gør denne algoritme hurtige end Minimumsort (50%). Alligevel kan algoritmen ikke siges at være speciel hurtig, men i stedet simpel, kort, konkret!

Shellsort

Som du sikkert har opdaget er det største problem med algoritmerne indtil nu at de kun laver byt over relativ korte distancer. Insertionsort er lidt bedre her, men vi kan ikke li' alle de skub den laver. Shellsort handler her lidt som Bubble-Up, men har den store fordel at den bytter elementer over større distancer. Dette vil i næsten hvert tilfælde være af stor fordel. Distance skal i dette sammenhænge ikke forstås som stor modstand - computeren er ligeglad om element 1 skal byttes med nr. 2 eller nr. 1000! Shellsort fastlægger til at starte med en fast distance og sammenligner elementer der ligger i en afstand på denne distance. Derefter bliver distancen forkortet og sorteringen foregår igen - indtil distance = 1.

procedure ShellSort; 
var 
  k, j, h, v: integer; 
begin 
  h := 1; 
  repeat 
    h := (3 * h) + 1; 
  until h > 10000; 
  repeat 
    h := (h div 3); 
    for k := (h + 1) to 10000 do begin 
      v := talarray[k]; 
      j := k; 
      while ((j > h) and (talarray[j - h] > v)) do begin 
        talarray[j] := talarray[j-h]; 
        dec(j, h); 
      end; 
      talarray[j]:= v; 
    end; 
  until h = 1; 
end;

Variablen h betegner distancen. Du kan selv bestemme med hvor stor en distance Shellsort skal begynde at sammenligne. Hvis du begyndte med en distance på 1 så var algoritmen identisk med Bubble-Up! Det har dog vist sig at være en god idé at vælge en begyndelsesdistance som svarer til omkring en tredjedel af antal elementer. Første repeat-lykke og første kommando sørger for at skabe en distance som passer til antal elementer. Da vi kender antallet (10000) er denne frem-finding ikke særlig gunstig og kunne også "hardcodes". For-k-lykken starter i elementet 'distance + 1', går fremad med arrayets ende og sammenligner derved elementet med element 'k - distance'. Gennem denne grovsortering opnås gunstige forudsætninger for de senere sorteringer med distance = 1 som den sidste.
Shellsort kan absolut holde med store komplicerede algoritmer. Dvs. Shellsort er slet ikke så hurtig som fx Quicksort, men ligger i samme kategorie, og byder en optimal kompromis mellem integritet og kompleksitet. Den er go' hvis du lige skal have en grid gennemsorteret!

Quicksort

Nu kommer vi til en af de mest anvendte sorteringsalgoritmer - quicksort. Quicksort er noget mere kompliceret end minimumsort og bubble-up, men til gengæld også much more powerfull! Den blev først opfundet engang i 60'erne, men den er simpelthen så lynende hurtig at den er mega udpræget. For at forstå quicksort skal du vide noget om rekursiv programmering. En rekursiv funktion er en funktion der kalder sig selv, og hvis du ikke i forvejen ved hvad det er så kan jeg anbefale den udmærkede artikel "Begynder rekursion" af Jens Borrisholt.
Quicksort tar udgangspunkt i et element i midten af arrayen. Til "venstre" side for denne søger den så efter et større og på "højre" side efter et mindre element. Har den fundet de to elementer, så bytter den dem. Dette gentages indtil venstre siden indeholder alle de mindre og højre alle de større elementer (tal). Derefter bliver samme princip anvendt på de to halvdele enkeltvis. Den rekursive proces gentager sig indtil hele arrayet er sorteret!

procedure Quicksort;

  procedure Qsort_rek(venstre, hoejre: integer);  //underprocedure
  var
    midti, h, j, tempint: integer;
  begin
    h := venstre;
    j := hoejre;
    midti := talarray[(venstre+hoejre) div 2]; 
    repeat
      while talarray[h] < midti  do
        inc(h);
      while talarray[j] > midti do
        dec(j);
      if h <= j then begin
        tempint := talarray[h];	//
        talarray[h] := talarray[j]; 	// trekantsbyt 
        talarray[j] := tempint;	//
        inc(h);
        dec(j);
      end;
    until h > j;
    if venstre < j then
      Qsort_rek(venstre, j);
    if hoejre > h then
      Qsort_rek(h, hoejre);
    end;

begin
  Qsort_rek(1, 9999); 
end;

Quicksort består i mit eksempel af to procedurer. Den ene har jeg for en nemhedsskyld integreret i den anden som underprocedure. Det betyder at kun Quicksort har adgang til Qsort_rek. Fordelen kan være at en underprocedure har adgang til moderprocedurens variable. Her er det gjord for en nemheds skyld.
Moderproceduren sætter kun den rekursive procedure igang men passende parametre. Det første der sker i den rekursive procedure er at variablen "midti" får tildelt værdien af et element der ligger næste i midten af arrayet. En repeat-lykke i forbindelse med 2 while-lykker sørger dernæst for at smide de små elementer på venstre og de store på højre side. Så snart det er gennemført kalder proceduren sig selv 2 gange, denne gang med parametre der angiver venstre hhv. højre side af arrayet.
Godt nok laver Quicksort også en masse sammenligninger, men meget færre ombytninger end de andre algoritmer. Man kan deraf konkludere at det er ombytninger der især koster tid.

Sorteringstider

Sorteringstider er selvfølgelig vigtige. Ved sortering af et array med 100000 elementer (random-tal) opnår algoritmerne følgende tider på min computer (p3 550MHz):
Bubble-Up: 82 sek. Minimumsort: 45 sek. Insertionsort: 24 sek. Shellsort: 0,96 sek. Quicksort: 0,38 sek.
Tidsforskellen er som du måske allerede har regnet ud meget mindre ved færre elementer. Bubble-Up, Minimumsort og Quicksort har jeg undersøgt nøje på deres sorteringstids-udvikling. Du kan downloade et demoprogram, som viser algortimernes sorteringstidsvækst og antal byt her:
http://www.wwmnet.de/dev/informatik/sorteringsalgoritmer/sorteringsalgoritmer.zip
Til skrivende stund har jeg kun implementeret de tre algoritmer, men muligvis er det flere når du downloader filen.

Andre algoritmer

Desværre har jeg ikke nok erfaring til at beskrive yderlige sorteringsalgoritmer. Men med Minimumsort, Shellsort og/eller Quicksort har du et utrolig mægtigt værktøj i hænderne ved programmering i Delphi. Algoritmerne kan selvfølgelig omskrives til andre sprog uden problemer. Quicksort findes også i flere yderlig optimerede versioner.
Det skal dog siges at der blandt sorteringsalgoritmer aldrig er et totalt non plus ultra! De har alle sammen deres fordele og ulemper - selv den sløve Bubble-Up, den er nem at huske :-). Hvis du for alvor skal til at sortere store datamængder fx egen database eller lign. kunne algoritmerne HeapSort, MergeSort, SwapSort og optimerede versioner af QuickSort være interessante. Hvis du betragter en ekstrem situation i hvilken kun to elementer skal sorteres så er det indlysende at en kompakt algoritme som Bubble-Up vinder overfor de store, da der kun sker én eneste sammenligning og ét byt. Algoritmerne har yderlige deres særtræk idet de belaster computer på forskellige måder. Quicksort fx er kendt for at belaste Stack-hukommelsen i høj grad.
Happy sorting!

Hvad synes du om denne artikel? Giv din mening til kende ved at stemme via pilene til venstre og/eller lægge en kommentar herunder.

Del også gerne artiklen med dine Facebook venner:  

Karma barometer (30 dage)

IT jobs | Kontakt | Om Udvikleren.dk | Om karma | IT nyheds arkiv | Annoncering

X