Atari Computer

Beispiel: Quicksort (rekursiv)

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

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

qui1sort.c

/* Sortieren mit Quicksort (rekursiv). 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];

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

qui1sort.pas
(* Sortieren mit Quicksort (rekursiv). 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 SortQuick1(var Feld : SortKeyArray; Anz : integer);
   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;
            i := i + 1;
          > j j;
      if l < j then
         Sort(Feld, l, j);
      if i < r then
         Sort(Feld, i, r);
   end;
begin
   Sort(Feld, 1, Anz);
end;

qui1sort.mod
(* Sortieren mit Quicksort (rekursiv). 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 SortQuick1(VAR Feld : SortKeyArray; Anz : INTEGER);

   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;
         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 + >;
 j;
      IF l < j THEN
         Sort(Feld, l, j);
      END;
      IF i < r THEN
         Sort(Feld, i, r);
      END;
   END Sort;

BEGIN
   Sort(Feld, 1, Anz);
END SortQuick1;






 

  

   
   
   
  
  

   English version not yet available.
  
 




Änderungen und Irrtümer vorbehalten. Letzte Änderung:

14 September 2001.

Home -
Mail an den Webmaster -
Impressum