/* Example quicksort program - more efficient versions of this are
possible - see Knuth or Sorting and Searching Algorithms: A Cookbook
for details */

#include <stdio.h>

enum {
    ARRAY_LEN= 14
};

void sortit (int [], int, int);
/* Performs the sort */
int partition (int [], int, int);
/* Find a pivot and partition the array */

int main()
{
    int array [ARRAY_LEN]= {9,5,11,1,3,13,45,14,7,22,100,5,7,102};
    int i;
    for (i= 0; i < ARRAY_LEN; i++) {
        printf ("%d ",array[i]);
    }
    printf ("\n");
    sortit(array, 0, ARRAY_LEN - 1);
    for (i= 0; i < ARRAY_LEN; i++) {
        printf ("%d ",array[i]);
    }
    printf ("\n");
    return 0;
}

void sortit (int sort [], int left, int right)
/* Sort an array of ints which has elements beginning at 'left' and
ending at 'right' */
{
    int pivot;
    if (left >= right)  /* We must have at least two elements to sort */
        return;
    pivot= partition (sort, left, right);
    sortit (sort, left, pivot - 1); /* Call the sort again with the left part*/
    sortit (sort, pivot+1, right); /* And with the right part */
}

int partition (int sort [], int left, int right)
/* Take one number as the "pivot" and put all numbers less than the pivot
on the left and all numbers greater on the right - return the position of
the pivot */
{
    /* In this case, we're going to take the left most element in our array
as the pivot - we're going to leave it there until everything else is sorted
out and then swap it into it's correct place */
    int i;
    int pivot_pos;  /* Position of our pivot */
    int temp;      /* Used for swaps */

    /* Move across the partition moving things left or right */
    /* Sort [left] will contain our pivot element - we'll swap it
    into place at the end */
    pivot_pos= left;  
    for (i= left+1; i <= right; i++) {
        /* If this element is to be left of the pivot then move the
        pivot position on one and swap it into position with the
        element at the new pivot position - remember that the
        element at the final pivot postion is swapped with the pivot*/
        if (sort[i] < sort[left]) {
            pivot_pos++;    /* Move the pivot position right */
            temp= sort[i];  /* And swap our element with the pivot position */
            sort[i]= sort[pivot_pos];
            sort[pivot_pos]= temp;
        }
    }
    /* Now swap our pivot into place */
    temp= sort[left];
    sort[left]= sort[pivot_pos];
    sort[pivot_pos]= temp;
    return pivot_pos;
}