This is the smartest stack handler in Quicksort that I could find.

I moved the stack size back to the default (which I believe is 1 MB), and it passed every input type test up to 1,234,567 EXCEPT descending - crashed on that one, even at 12,3456.

All this testing was with doubles. Times of the runs are included with the code, and swing dramatically. This program is pretty close to what your instructor had given you, in it's overall design. (it moves the pivot, etc.).

#include <stdio.h> #include <stdlib.h> #include <time.h> /* from: The Practice of Programming (pp: 32-34) * by: Brian W. Kernighan and Rob Pike */ /* swap: interchange v[i] and v[j] */ void swap( double v[], int i, int j ) { double tmp; tmp = v[i]; v[i] = v[j]; v[j] = tmp; } /* quicksort: sort v[0]..v[n-1] into increasing * order */ void quicksort( double v[], int n ) { int i = 0, last = 0; if ( n <= 1 ) /* nothing to do */ return; //not moving the pivot, means that v[0] becomes the pivot, with every recursive call //swap( v, 0, rand() % n ); // move pivot elem //to v[0] for ( i = 1; i < n; i++ ) /* partition */ if ( v[i] < v[0] ) swap( v, ++last, i ); swap( v, 0, last ); /* restore pivot */ quicksort( v, last ); /* sort smaller values */ quicksort( v+last+1, n-last-1 ); /* sort larger values */ } void print_array( const double array[], int elems ) { int i; for ( i = 0; i < elems; i++ ) printf("%15.2f ", array[i] ); printf("\n"); } //1234567 random: 0.2 seconds, all ascending: 903 seconds, all descending (NUM==12345):0.2 seconds //1234567 all equal: 906 seconds. #define NUM 1234567 int main( void ) { double *arr=malloc(NUM * sizeof(double)); if(!arr) { printf("Error allocting memory!\n"); return 1; } for(int i=0;i<NUM;i++) { //arr[i]= rand() % 10000+1; //all random //arr[i]=i*3.14159265358979; //all ascending //arr[i]=(NUM-i+1)*3.14159265358979; //all descending arr[i]= NUM+0.12; //all equal } /* commented out to aid in predictability * srand( (unsigned int) time(NULL) ); */ //print_array(arr, NUM); //getchar(); clock_t timer=clock(); quicksort(arr, NUM); timer=(clock()-timer); print_array(arr, NUM); printf("Elapsed time: %f\n",(double) timer/CLOCKS_PER_SEC); return EXIT_SUCCESS; }

If you want to make it work, even with a bad pivot, maybe simply swap some array values. Even swapping 100 random array[random index] numbers, would do wonders for a sort of 50,000 numbers, imo.

Thanks for the interesting thread. />/> Let me know how it works out.

This post has been edited by **Adak**: 07 February 2013 - 08:57 AM