Programmieren

TOS - Algorithmen - Beispiele - weitere Informationen

Beispiel: Mergesort

Die folgenden Beispiele zeigen das Sortieren von Feldern, deren Speicherbedarf den Rechnerspeicher übersteigt mittels Mergesort.

mergsort.c

/* Sortieren mit Mergesort fuer Felder, deren Speicherbedarf den */
/* Rechnerspeicher uebersteigt. Da der Datentyp erst bei einer   */
/* konkreten Anwendung feststeht, ist der Sortieralgorithmus nur */
/* als Beispiel und nicht als Modul programmiert.                */

#include 

#define MAX_SORT_ELT 8000

typedef long SortKeyType;
typedef SortKeyType SortKeyArray[MAX_SORT_ELT];

SortKeyArray Feld;

static void Sort(SortKeyArray Feld, int Anz)
{
   /* waehle einen Sortieralgorithmus */
}

static void Zerlege(FILE *a,FILE *b,FILE *c)
{  int Anz;

   Anz = (int)fread(Feld, sizeof(SortKeyType), MAX_SORT_ELT, c);
   if (Anz > 0)
   {
      Sort(Feld, Anz);
      fwrite(Feld, sizeof(SortKeyType), Anz, a);
      Anz = (int)fread(Feld, sizeof(SortKeyType), MAX_SORT_ELT, c);
      if (Anz > 0)
      {
         Sort(Feld, Anz);
         fwrite(Feld, sizeof(SortKeyType), Anz, b);
      }
   }
}

static void Verschmelze(FILE *a,FILE *b,FILE *c)
{  int Fertig;
   SortKeyType WertA,WertB;

   Fertig = 0;
   if (fread(&WertA, sizeof(SortKeyType), 1, a) == 0)
   {
      while (fread(&WertB, sizeof(SortKeyType), 1, b) == 1)
         fwrite(&WertB, sizeof(SortKeyType), 1, c);
      Fertig = 1;
   }
   else
   {
      if (fread(&WertB, sizeof(SortKeyType), 1, b) == 0)
      {
         fwrite(&WertA, sizeof(SortKeyType), 1, c);
         while (fread(&WertA, sizeof(SortKeyType), 1, a) == 1)
            fwrite(&WertA, sizeof(SortKeyType), 1, c);
         Fertig = 1;
      }
   }
   while (!Fertig)
   {
      if (WertB < WertA)
      {
         fwrite(&WertB, sizeof(SortKeyType), 1, c);
         if (fread(&WertB, sizeof(SortKeyType), 1, b) == 0)
         {
            fwrite(&WertA, sizeof(SortKeyType), 1, c);
            while (fread(&WertA, sizeof(SortKeyType), 1, a) == 1)
               fwrite(&WertA, sizeof(SortKeyType), 1, c);
            Fertig = 1;
         }
      }
      else
      {
         fwrite(&WertA, sizeof(SortKeyType),1,c);
         if (fread(&WertA, sizeof(SortKeyType), 1, a) == 0)
         {
            fwrite(&WertB, sizeof(SortKeyType), 1, c);
            while (fread(&WertB, sizeof(SortKeyType), 1, b) == 1)
               fwrite(&WertB, sizeof(SortKeyType), 1, c);
            Fertig = 1;
         }
      }
   };
}

void SortMergesort(char *FileName)
{  FILE *a,*b,*c;

   c=fopen(FileName,"rb");
   a=fopen("temp1","wb");
   b=fopen("temp2","wb");
   Zerlege(a,b,c);
   fclose(a);
   fclose(b);
   fclose(c);
   a=fopen("temp1","rb");
   b=fopen("temp2","rb");
   c=fopen(FileName,"wb");
   Verschmelze(a,b,c);
   fclose(a);
   fclose(b);
   fclose(c);
}

mergsort.pas

(* Sortieren mit Mergesort fuer Felder, deren Speicherbedarf den *)
(* Rechnerspeicher uebersteigt. Da der Datentyp erst bei einer   *)
(* konkreten Anwendung feststeht, ist der Sortieralgorithmus nur *)
(* als Beispiel und nicht als Modul programmiert.                *)

const
   MaxSortElt=80;

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

procedure SortMergesort(FileName:string);
   var
      a, b, c : SortKeyFile;
   procedure Zerlege(var a:SortKeyFile;var b:SortKeyFile;var c:SortKeyFile);
      var
         Anz, i : integer;
         Feld : SortKeyArray;
      procedure Sort(var Feld:SortKeyArray; Anz:integer);
         begin
            (* waehle einen Sortieralgorithmus *)
         end;
      begin
         Anz := 0;
         while not eof(c) and (Anz 0) then
         begin
            Sort(Feld, Anz);
            for i:=1 to Anz do
            begin
               a^ := Feld[i];
               put(a);
            end;
            Anz := 0;
            while not eof(c) and (Anz 0) then
            begin
               Sort(Feld, Anz);
               for i:=1 to Anz do
               begin
                  b^ := Feld[i];
                  put(b);
               end;
            end;
         end;
      end;
   procedure Verschmelze(var a:SortKeyFile;var b:SortKeyFile;var c:SortKeyFile);
      var
         Fertig : boolean;
         WertA, WertB : SortKeyType;
      begin
         Fertig := false;
         if eof(a) then
         begin
            while not eof(b) do
            begin
               get(b);
               c^ := b^;
               put(c);
            end;
            Fertig := true;
         end
         else
         begin
            if eof(b) then
            begin
               while not eof(a) do
               begin
                  get(a);
                  c^ := a^;
                  put(c);
               end;
               Fertig := true;
            end;
         end;
         while not Fertig do
         begin
            if (b^ < a^) then
            begin
               c^ := b^;
               put(c);
               if not eof(b) then
               begin
                  get(b);
               end
               else
               begin
                  c^ := a^;
                  put(c);
                  while not eof(a) do
                  begin
                     get(a);
                     c^ := a^;
                     put(c);
                  end;
                  Fertig := true;
               end;
            end
            else
            begin
               c^ := a^;
               put(c);
               if not eof(a) then
               begin
                  get(a);
               end
               else
               begin
                  c^ := b^;
                  put(c);
                  while not eof(b) do
                  begin
                     get(b);
                     c^ := b^;
                     put(c);
                  end;
                  Fertig := true;
               end;
            end;
         end;
      end;
   begin
      reset(c,FileName);
      rewrite(a,'temp1');
      rewrite(b,'temp2');
      Zerlege(a,b,c);
      close(a);
      close(b);
      close(c);
      reset(a,'temp1');
      reset(b,'temp2');
      rewrite(c,FileName);
      Verschmelze(a,b,c);
      close(a);
      close(b);
      close(c);
   end;

English version not yet available.