Monday, October 31, 2005

shortest code for quick sort

#include <stdafx.h>

int A[] = { 99, 43, 22, 17, 57, 32, 43, 19, 26, 48, 87, 12, 75, 0 };
const int numEntries = sizeof(A)/sizeof(int);
void quicksort (int a[], int lo, int hi)
{

// lo is the lower index, hi is the upper index
// of the region of array a that is to be sorted
int i=lo, j=hi, h;
int x=a[(lo+hi)/2];

// printf("\npivot:%d",x);

// partition
do
{
while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);

// recursion
if (lo<j) quicksort(a, lo, j);
if (i<hi) quicksort(a, i, hi);
}


void qksort() {
quicksort(A,0,numEntries - 1);
}

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




int main(void) {
printf("Before sorting, the entries of A are:\n");
printArray();
qksort();
printf("After sorting, the entries of A are:\n");
printArray();
getchar();
}


/*


Before sorting, the entries of A are:
99 43 22 17 57 32 43 19 26 48 87 12 75 0
After sorting, the entries of A are:
0 12 17 19 22 26 32 43 43 48 57 75 87 99


*/

0 Comments:

Post a Comment

<< Home