/****************************/
/* Quicksort: Erste Version */
/****************************/

/*----------*/
/* Includes */
/*----------*/

#include <exec/types.h>
#include <stdio.h>

#define REG register
#define BOOLEAN BOOL
#define CHAR char

#define CLS   fputchar ( 0xc )
#define TASTE printf("-- Return --"); gets( hilf )


char hilf[ 80 ];

WORD a[5000];   /* globales, zu sortierendes Array */


VOID quicksort(links,rechts)
WORD links,rechts;
{
   register WORD i,j,save;

   i  = links;
   j  = rechts;

   save = a[ (WORD) (i+j)/2 ];

   while(i!=j)
   {
      while((a[j]>save)&&(i<j))  --j;
      a[i] = a[j];

      while((a[i]<=save)&&(i<j)) ++i;
      a[j] = a[i];
   }

   a[i] = save;

   if (links<(i-1))  quicksort(links,i-1);
   if ((i+1)<rechts) quicksort(i+1,rechts);
}
 

VOID main()
{
   register WORD i;

   CLS;

   puts("* Erzeugen und Eintragen von 5000 Zufallszahlen.");

   for(i=0;i<5000;i++)
      a[i]= (unsigned int) rand() % 9999; 

   puts("* Taste drücken, um zu sortieren ...");
   TASTE;

   puts("\n* Start von  Quicksort !!");
   quicksort(0,4999);
   puts("\n* Fertig !!");

   puts("\n* Die ersten 20 ersten Elemente:\n");

   for(i=0;i<20;i++)
   {
      printf("%3d. Sort=%4d\n",
             i,a[i]);
   }

   TASTE;

   /*------------------------------------------------------*/
   /* für ganz skeptische: Reihenfolge nochmals überprüfen */
   /*------------------------------------------------------*/

   for(i=0;i<4999;i++)
      if(a[i]>a[i+1]) 
         printf("Fehler bei Element %d\n",i+1);
   
}