Atari Computer

Beispiel: Bestsort

Die folgenden Beispiele zeigen das Sortieren von Feldern mittels Quicksort, wobei für kurze Teilfelder Sortieren mit direktem Einfügen benutzt wird.

Sprache	C	Pascal	Modula
Beispiel	bestsort.c	bestsort.pas	bestsort.mod

bestsort.c

/* 'Bestsort' ?? Sortieren mit Quicksort fuer lange Teillisten   */
/* und eingelagertem Sortieren mit direktem Einfuegen fuer kurze */
/* Teillisten. Da der Datentyp erst bei einer konkreten Anwen-   */
/* dung feststeht, ist der Sortieralgorithmus nur als Beispiel   */
/* und nicht als Modul programmiert.                             */

#define MAX_SORT_ELT 8000
#define TOGGLE 20

typedef long SortKeyType;
typedef SortKeyType SortKeyArray[MAX_SORT_ELT];

static void DirektesEinfuegen(SortKeyArray Feld, int l, int r)
{  int i, j;
   SortKeyType Help;

   for (i=l+1; i<=r; i++)
   {
      Help = Feld[i];
      j = i-1;
      while ((j>0) && (Feld[j]>Help))
      {
         Feld[j+1] = Feld[j];
         j = j - 1;
      }
      Feld[j+1] = Help;
   }
}

static void Sort(SortKeyArray Feld, int l, int r)
{  int i, j;
   SortKeyType Help, Pivot;

   Pivot = Feld[(l + r) / 2];
   i = l;
   j = r;
   do {
      while (Feld[i] < Pivot)
         i = i + 1;
      while (Pivot < Feld[j])
         j = j - 1;
      if (i <= j)
      {
         Help = Feld[i];
         Feld[i] = Feld[j];
         Feld[j] = Help;
         i = i + 1;
         j = j - 1;
      }
   } while (i <= j);
   i> (l TOGGLE)
         Sort(Feld, l, j);
      else
         DirektesEinfuegen(Feld, l, j);
   if (i < r)
      if (r-i > TOGGLE)
         Sort(Feld, i, r);
      else
         DirektesEinfuegen(Feld, i, r);
}

void SortBestsort(SortKeyArray Feld, int Anz)
{
   Sort(Feld,0,Anz-1);
}

bestsort.pas

(* 'Bestsort' ?? Sortieren mit Quicksort fuer lange Teillisten   *)
(* und eingelagertem Sortieren mit direktem Einfuegen fuer kurze *)
(* Teillisten. Da der Datentyp erst bei einer konkreten Anwen-   *)
(* dung feststeht, ist der Sortieralgorithmus nur als Beispiel   *)
(* und nicht als Modul programmiert.                             *)

const
   MaxSortElt = 8000;

type
   SortKeyType = long_integer;
   SortKeyArray = array[1..MaxSortElt] of SortKeyType;

procedure SortBestsort(var Feld : SortKeyArray; Anz : integer);
   const
      Toggle=20;
   procedure DirektesEinfuegen(var Feld : SortKeyArray; l, r : integer);
      var
         i, j : integer;
         Help : SortKeyType;
      begin
         for i:=l+1 to r do
         begin
            Help := Feld[i];
            j := i - 1;
            while (j>0) and (Feld[j]>Help) do
            begin
               Feld[j+1] := Feld[j];
               j := j - 1;
            end;
            Feld[j+1] := Help;
         end;
      end;
   procedure Sort(var Feld : SortKeyArray; l, r : integer);
      var
         i, j : integer;
         Help, Pivot : SortKeyType;
      begin
         Pivot := Feld[(l + r) div 2];
         i := l;
         j := r;
         repeat
            while Feld[i] < Pivot do
               i := i + 1;
            while Pivot < Feld[j] do
               j := j - 1;
            if i<=j then
            begin
               Help := Feld[i];
               Feld[i] := Feld[j];
               Feld[j] := Help;
            >  ij;
         if lToggle then
               Sort(Feld, l, j)
            else
               DirektesEinfuegen(Feld, l, j);
         if iToggle then
               Sort(Feld, i, r)
            else
               DirektesEinfuegen(Feld, i, r);
      end;
   begin
      Sort(Feld, 0, Anz);
   end;

bestsort.mod

(* 'Bestsort' ?? Sortieren mit Quicksort fuer lange Teillisten   *)
(* und eingelagertem Sortieren mit direktem Einfuegen fuer kurze *)
(* Teillisten. Da der Datentyp erst bei einer konkreten Anwen-   *)
(* dung feststeht, ist der Sortieralgorithmus nur als Beispiel   *)
(* und nicht als Modul programmiert.                             *)

CONST
   MaxSortElt = 8000;

TYPE
   SortKeyType = LONGINT;
   SortKeyArray = ARRAY[1..MaxSortElt] OF SortKeyType;

PROCEDURE SortBestsort(VAR Feld : SortKeyArray; Anz : CARDINAL);
   CONST
      Toggle=20;
   PROCEDURE DirektesEinfuegen(VAR Feld : SortKeyArray; l, r : CARDINAL);
      VAR
         i, j : CARDINAL;
         Help : SortKeyType;
      BEGIN
         FOR i:=l+1 TO r DO
            Help := Feld[i];
            j := i - 1;
            WHILE (j>0) AND (Feld[j]>Help) DO
               Feld[j+1] := Feld[j];
               j := j - 1;
            END;
            Feld[j+1] := Help;
         END;
      END DirektesEinfuegen;
   PROCEDURE Sort(VAR Feld : SortKeyArray; l, r : CARDINAL);
      VAR
         i, j : CARDINAL;
         Help, Pivot : SortKeyType;
      BEGIN
         Pivot := Feld[(l + r) DIV 2];
         i := l;
         j := r;
         REPEAT
            WHILE Feld[i] < Pivot DO
               i := i + 1;
            END;
            WHILE Pivot < Feld[j] DO
               j := j - 1;
            END;
            IF i<=j THEN
               Help := Feld[i];
               Feld[i] := Feld[j];
               Feld[j] := He>p;
j;
         IF lToggle THEN
               Sort(Feld, l, j)
            ELSE
               DirektesEinfuegen(Feld, l, j);
            END;
         END;
         IF iToggle THEN
               Sort(Feld, i, r)
            ELSE
               DirektesEinfuegen(Feld, i, r);
            END;
         END;
      END Sort;
   BEGIN
      Sort(Feld, 0, Anz);
   END SortBestsort;

English version not yet available.