#include <stdio.h>

/*

This program is a simple implementation of quicksort
 as described by Knuth's The Art of Computer Programming in chapter 5

Use:
      $ make quicksort
      cc     quicksort.c   -o quicksort
      
      $ ./quicksort
       TEST 1:
      before sorting:
       [67, 6, 42, 55, 41, 54, 99, 50, 91, 58]
      after sorting:
       [6, 41, 42, 50, 54, 55, 58, 67, 91, 99]
      
       TEST 1:
      before sorting:
       [481, 689, 490, 98, 459, 679, 986, 990, 701, 868, 630, 383, 415, 299,
        349, 346]
      after sorting:
       [98, 299, 346, 349, 383, 415, 459, 481, 490, 630, 679, 689, 701, 868,
        986, 990]
	  
       TEST 3:
      before sorting:
       [3, 0, 3, 7, 2, 6, 2, 8, 4, 6]
      after sorting:
       [0, 2, 2, 3, 3, 4, 6, 6, 7, 8]



  Sam Auciello | Marlboro College
  Apr 2012     | opensource.org/licenses/MIT

*/

void printlist(int* list, int n) {
  /* print the first n integers after the list array pointer
   * in the format of a ruby/javascript array or python list
   */
  
  printf(" [");
  int i;
  for (i=0; i<n; i++) {
	if (i > 0) printf(", ");
	printf("%i", list[i]);
  }
  printf("]\n");
}

void swap(int* list, int i, int j) {
  /* swap the value of the ith integer after the list array pointer
   * with the value of the jth integer after the list array pointer
   */
  
  int tmp = list[i];
  list[i] = list[j];
  list[j] = tmp;
}

void quicksort(int* list, int n) {
  /* rearange the first n integers after the list array pointer
   * so that they are in non-decreasing order
   */
  
  if (n > 1) { // base case : do nothing to lists of 1 or fewer elements
	
	// initialize i and j to point to the second and last elements respectively
	int i = 1;
	int j = n - 1;
	
	// until i and j pass each other or meet
	while (j >= i) {
	  
	  // move i forward to the first element greater than list[0]
	  while (list[i] <= list[0] && i < n) i++;
	  
	  // move j backard to the last element less than list[0]
	  while (list[j] >= list[0] && j > 0) j--;
	  
	  // swap the i and j unless they've passed each other
	  if (j > i) swap(list, i, j);
	}
	
	// swap list[0] up to the middle
	swap(list, 0, j);
	
	// recursively sort the lists before and after the middle
	quicksort(list, j);
	quicksort(&list[j+1], n - j - 1);
  }
}

int main() {
  /* Three tests to demonstrate that the sorting works.
   * The second one is 16 random numbers between 0 and 1000
   *  in homage to knuths example data.
   * The third was engineered to have repeated numbers to demonstrate
   *  that the implementation could handle equal elements.
   */
  
  // generated with "10.times.map{rand 100}" in ruby
  printf(" TEST 1:\n");
  int testList[10] = {67, 6, 42, 55, 41, 54, 99, 50, 91, 58};
  printf("before sorting:\n");
  printlist(testList, 10);
  quicksort(testList, 10);
  printf("after sorting:\n");
  printlist(testList, 10);

  // generated with "16.times.map{rand 1000}" in ruby
  printf("\n TEST 2:\n");
  int testList2[16] = {481, 689, 490, 98, 459, 679, 986, 990, 701, 868, 630,
                       383, 415, 299, 349, 346};
  printf("before sorting:\n");
  printlist(testList2, 16);
  quicksort(testList2, 16);
  printf("after sorting:\n");
  printlist(testList2, 16);

  // generated with "10.times.map{rand 10}" in ruby
  printf("\n TEST 3:\n");
  int testList3[10] = {3, 0, 3, 7, 2, 6, 2, 8, 4, 6};
  printf("before sorting:\n");
  printlist(testList3, 10);
  quicksort(testList3, 10);
  printf("after sorting:\n");
  printlist(testList3, 10);
  
  return 0;
}