// TinyC implementation of the world famous quicksort algorithm by Prof. C.A.R. Hoare
// Beware of the free-memory spaces on MT chips!


#define NUM	20   // number of data to test
#define DELAY	100

int	A[NUM];	     // storage of numbers for sorting
int	N;           // indicator for no. of times qsort() has been called


main()
{
   int   i;

   setcomm(9600); // output to serial port as well

loop { // this loop statement repeats the whole process indefintely, remove it for the program to run once!

   N = 1;	  // init N to find out how many times quicksort() has been called
   // generate NUM random numbers
   for(i=0; i < NUM; i++) {
      A[i] = random();
   }

   // show them out if you want to see the unsorted array!
   separator();
   for(i=0; i < NUM; i++) {
      writei('d', A[i], DELAY); // o/p to LCD or 7-Segment display 
      writei(232, A[i], DELAY); // o/p to serial port
      writec(232, 13, 0);       // o/p to serial port, NL
      writec(232, 10, 0);       // o/p to serial port, LF
   }

   // call quicksort() to do the sorting, this will take a while for a large array
   quicksort(0, NUM-1);

   delay(2000);	// pause here to see the value of N

   // show the sorted array
   separator();
   for(i=0; i < NUM; i++) {
      writei('d', A[i], DELAY); // o/p to LCD or 7-Segment display 
      writei(232, A[i], DELAY); // o/p to serial port
      writec(232, 13, 0);       // o/p to serial port, NL
      writec(232, 10, 0);       // o/p to serial port, LF
   }
	
   writes("end", 1000);

} // closing bracket of the loop statement to run indefinitely!

}

separator()
{
   writec(232, '*', DELAY); // o/p to serial port
   writec(232, 13,  0);     // o/p to serial port, NL
   writec(232, 10,  0);     // o/p to serial port, LF
}

quicksort(left, right)
{
  int	i, j, x, y;

  writei('d', N++, 10);	// just an indicator to show quicksort() is running!

  i = left; 
  j = right;
  x = A[(left+right)/2];

  loop {
/* when using 'loop' statements!
    loop { if((A[i] >= x) || (i >= right)) break; i++; }
    loop { if((x >= A[j]) || (j <=  left)) break; j--; }
*/
    while((A[i] < x) && (i < right)) i++;
    while((x < A[j]) && (j >  left)) j--;
    if(i <= j) {
      y    = A[i];
      A[i] = A[j];
      A[j] = y;
      i++; 
      j--;
    }
    if(i > j) break;
  } 
  if(left < j)  quicksort(left, j);
  if(i < right) quicksort( i, right);
}