/*--------------------------------------------------------------------*/
/* testsort.c                                                         */
/* Author: Bob Dondero                                                */
/* A program to demonstrate execution profiling.                      */
/*--------------------------------------------------------------------*/

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

/*--------------------------------------------------------------------*/

/* The number of elements in aiNums. */
enum {MAX_SIZE = 10000000};

/* This large array doesn't fit on the stack, so place it
   in the bss section. */
static int aiNums[MAX_SIZE];

/*--------------------------------------------------------------------*/

/* Fill aiNums with iSize random integers. */

static void fillArray(int aiNums[], int iSize)
{
   int i;
   for (i = 0; i < iSize; i++)
      aiNums[i] = rand();
}

/*--------------------------------------------------------------------*/

/* Swap aiNums[iOne] and aiNums[iTwo]. */

static void swap(int aiNums[], int iOne, int iTwo)
{
   int iTemp;
   iTemp = aiNums[iOne];
   aiNums[iOne] = aiNums[iTwo];
   aiNums[iTwo] = iTemp;
}

/*--------------------------------------------------------------------*/

/* Divide aiNums[iLeft...iRight] into two partitions so elements
   in the first partition are <= elements in the second partition.
   Return the index of the element that marks the partition
   boundary. */

static int partition(int aiNums[], int iLeft, int iRight)
{
   int iFirst = iLeft-1;
   int iLast = iRight;

   while (1)
   {
      while (aiNums[++iFirst] < aiNums[iRight])
         ;
      while (aiNums[iRight] < aiNums[--iLast])
         if (iLast == iLeft)
            break;
      if (iFirst >= iLast)
         break;
      swap(aiNums, iFirst, iLast);
   }
   swap(aiNums, iFirst, iRight);
   return iFirst;
}

/*--------------------------------------------------------------------*/

/* Sort aiNums[iLeft...iRight] in ascending order. */

static void quicksort(int aiNums[], int iLeft, int iRight)
{
   if (iRight > iLeft)
   {
      int iMid = partition(aiNums, iLeft, iRight);
      quicksort(aiNums, iLeft, iMid - 1);
      quicksort(aiNums, iMid + 1, iRight);
   }
}

/*--------------------------------------------------------------------*/

/* Print the iSize elements of aiNums to stdout. */

static void printArray(int aiNums[], int iSize)
{
   int i;
   for (i = 0; i < iSize; i++)
      printf("%d\n", aiNums[i]);
}

/*--------------------------------------------------------------------*/

/* Fill an array of MAX_SIZE random integers, sort the integers in
   ascending order, and print the integers to stdout.  Return 0. */

int main(void)
{
   fillArray(aiNums, MAX_SIZE);
   quicksort(aiNums, 0, MAX_SIZE - 1);
   printArray(aiNums, MAX_SIZE);

   return 0;
}