/* quiksort.c */
/* An implementation of a quicksort algorithm. */

/* compiler directive */
#include <stdio.h>

/* function prototypes */
void quicksort(int input_array[], int top, int bottom);
int partition(int input_array[], int top, int bottom);
void display_array(int input_array[], int input_size);

int main()
{
  int nums[5] = {20, 31, 17, 47, 14};
  int nums_length = 5;

  printf("Unsorted Array:\n");
  display_array(nums, nums_length);

  quicksort(nums, 0, nums_length - 1);

  printf("Sorted Array:\n");
  display_array(nums, nums_length);
  return 0;
}

/* Quicksort procedure. Sorts an array of ints in descending order. */
void quicksort(int input_array[], int top, int bottom)
{
  int middle;
  
  if (top < bottom)
   {
    middle = partition(input_array, top, bottom);
    quicksort(input_array, top, middle);	/* sort top partition */
    quicksort(input_array, middle + 1, bottom); /* sort bottom partition */
   }
}

/* partitions input_array, returning middle index. Used by procedure quicksort. */
int partition(int input_array[], int top, int bottom)
{
  int x = input_array[top];
  int i = top - 1;
  int j = bottom + 1;
  int temp;

  do
   {
    /* move j towards top to the next element less than or equal to x. */
    do
     {
      j--;
     } while(x > input_array[j]);

    /* move j towards bottom to the next element greater than or equal to x. */
    do
     {
      i++;
     } while(x < input_array[i]);

    if (i < j)
     {
      /* switch elements at positions i and j. */
      temp = input_array[i];
      input_array[i] = input_array[j];
      input_array[j] = temp;
     }
   } while(i < j);	/* loop ends when i and j have met in the middle. */

   return j;	/* j and above represents top partition, below j is bottom partition. */
}

/* Function that simply displays each element of input_array. */
void display_array(int input_array[], int input_size)
{
  int i;
  
  for (i = 0; i < input_size; i++)
   {
    printf("%d ", input_array[i]);
   }
  printf("\n\n");
}