Programmieren

TOS - Algorithmen - Beispiele - weitere Informationen

Beispiel: Quicksort (iterativ)

Die folgenden Beispiele zeigen das Sortieren von Feldern mittels Quicksort in einer iterativen Form.

qui2sort.c

/* Sortieren mit Quicksort (iterativ). Da der Datentyp erst bei    */
/* einer konkreten Anwendung feststeht, ist der Sortieralgorithmus */
/* nur als Beispiel und nicht als  Modul programmiert.             */

#define MAX_SORT_ELT 8000

typedef long SortKeyType;
typedef SortKeyType SortKeyArray[MAX_SORT_ELT];

void SortQuick2(SortKeyArray Feld, int Anz)
{  int i, j, l, r;
   SortKeyType Help, Pivot;
   Stack x;
   StackData el;

   StackCreate(&x);
   el.l = 0;
   el.r = Anz-1;
   StackPush(&x, &el);
   do {
      StackPop(&x, &el);
      l = el.l;
      r = el.r;
      i = l;
      j = r;
      Pivot=Feld[(l + r) / 2];
      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);
      if (l < j)
      {
         el.l = l;
         el.r = j;
         StackPush(&x, &el);
      }
      if (i < r)
      {
         el.l = i;
         el.r = r;
         StackPush(&x, &el);
      }
   } while (!StackIsEmpty(x));
}

qui2sort.pas

(* Sortieren mit Quicksort (iterativ). Da der Datentyp erst bei    *)
(* einer konkreten Anwendung 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 SortQuick2(var Feld : SortKeyArray; Anz : integer);
var
   i, j, l, r : integer;
   Help, Pivot : SortKeyType;
   x : Stack;
   el : StackData;
begin
   StackCreate(x);
   el.l := 1;
   el.r := Anz;
   StackPush(x, el);
   repeat
      StackPop(x, el);
      l := el.l;
      r := el.r;
      i := l;
      j := r;
      Pivot := Feld[(l + r) div 2];
      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;
            i := i + 1;
            j := j - 1;
         end;
      until i > j;
      if l < j then
      begin
         el.l := l;
         el.r := j;
         StackPush(x, el);
      end;
      if i < r then
      begin
         el.l := i;
         el.r := r;
         StackPush(x, el);
      end;
   until StackIsEmpty(x);
end;

qui2sort.mod

(* Sortieren mit Quicksort (iterativ). Da der Datentyp erst bei    *)
(* einer konkreten Anwendung 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 SortQuick2(VAR Feld : SortKeyArray; Anz : INTEGER);
VAR
   i, j, l, r : CARDINAL;
   Help, Pivot : SortKeyType;
   x : Stack;
   el : StackData;
BEGIN
   StackCreate(x);
   el.l := 1;
   el.r := Anz;
   StackPush(x, el);
   REPEAT
      StackPop(x, el);
      l := el.l;
      r := el.r;
      i := l;
      j := r;
      Pivot := Feld[(l + r) DIV 2];
      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] := Help;
            i := i + 1;
            j := j - 1;
         END;
      UNTIL i > j;
      IF l < j THEN
         el.l := l;
         el.r := j;
         StackPush(x, el);
      END;
      IF i < r THEN
         el.l := i;
         el.r := r;
         StackPush(x, el);
      END;
   UNTIL StackIsEmpty(x);
END SortQuick2;

English version not yet available.