/*-------------------------------------------------------------------*/ /* testsort.c */ /* A program to demonstrate execution profiling. */ /*-------------------------------------------------------------------*/ #include #include #include #define MAX_SIZE 10000000 /* This large array doesn't fit on the stack, so place it in the bss section. */ int piArray[MAX_SIZE]; /*-------------------------------------------------------------------*/ void fillArray(int piArray[], int iSize) /* Fill piArray with iSize random integers. */ { int i; for (i = 0; i < iSize; i++) piArray[i] = rand(); } /*-------------------------------------------------------------------*/ void swap(int piArray[], int iOne, int iTwo) /* Swap piArray[iOne] and piArray[iTwo]. */ { int iTemp; iTemp = piArray[iOne]; piArray[iOne] = piArray[iTwo]; piArray[iTwo] = iTemp; } /*-------------------------------------------------------------------*/ int partition(int piArray[], int iLeft, int iRight) /* Divide piArray[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. */ { int iFirst = iLeft-1; int iLast = iRight; while (1) { while (piArray[++iFirst] < piArray[iRight]) ; while (piArray[iRight] < piArray[--iLast]) if (iLast == iLeft) break; if (iFirst >= iLast) break; swap(piArray, iFirst, iLast); } swap(piArray, iFirst, iRight); return iFirst; } /*-------------------------------------------------------------------*/ void quicksort(int piArray[], int iLeft, int iRight) /* Sort piArray[iLeft...iRight] in ascending order. */ { if (iRight > iLeft) { int iMid = partition(piArray, iLeft, iRight); quicksort(piArray, iLeft, iMid - 1); quicksort(piArray, iMid + 1, iRight); } } /*-------------------------------------------------------------------*/ void printArray(int piArray[], int iSize) /* Print the iSize elements of piArray to stdout. */ { int i; for (i = 0; i < iSize; i++) printf("%d\n", piArray[i]); } /*-------------------------------------------------------------------*/ int main(int argc, char *argv[]) /* Fill an array of MAX_SIZE random integers, sort the integers in ascending order, and print the integers to stdout. */ { fillArray(piArray, MAX_SIZE); quicksort(piArray, 0, MAX_SIZE - 1); /* printArray(piArray, MAX_SIZE); */ return 0; }