/* C, code from Numerical Recipes */ #include #include #include #include // 7 is the threshold defined in the book, so that's what I used #define M 7 // 50 is the limit defined in the book, so that's what I used #define NSTACK 50 void num_rec_sort(int n, TYPE arr[]) { // This code is from Numerical Recipes, with minor changes int i, ir=n, j, k, l=0, *istack; int jstack = 0; TYPE a; istack = new int[NSTACK]; // manage our own stack for(;;) { if(ir-l < M) { // Insertion sort when subarray small enough for(j=l+1; j=1; i--) { if(arr[i] <= a) break; arr[i+1]=arr[i]; } arr[i+1]=a; } if(jstack == 0) break; ir=istack[jstack--]; l=istack[jstack--]; } else { // quicksort when the subarray is large k=(l+ir)>>1; swap(arr[k], arr[l+1]); if(arr[l] > arr[ir]) { swap(arr[l], arr[ir]); } if(arr[l+1] > arr[ir]) { swap(arr[l+1], arr[ir]); } if(arr[l] > arr[l+1]) { swap(arr[l], arr[l+1]); } i=l+1; j=ir; a=arr[l+1]; for(;;) { do i++; while(arr[i] < a); do j--; while(arr[j] > a); if(j NSTACK) abort(); if(ir-i+1 >= j-1) { istack[jstack]=ir; istack[jstack-1]=i; ir=j-1; } else { istack[jstack]=j-1; istack[jstack-1]=l; l=i; } } } delete[] istack; } void test(int N) { if(N < 1) { cerr << "Input value " << N << " too small." << endl; return; } TYPE* data = new TYPE[N]; if(!data) { cerr << "Could not allocate data - " << N << " bytes." << endl; return; } for(int i=0; i" << endl; else { for(int i=0; i<10; ++i) test(atoi(argv[1])); } return 0; }