Hi! I'm a first semester computer science student, and i'm working on an extra credit assignment for my C++ class (although the code below is in C, it should be portable to C++). The assignment is to write a quicksort function using in-place sorting. I already have a working function below, however, I'd like to make it more efficient, if possible.

At first, I considered using an internal stack rather than recursion, however I'm not sure if that would be the best way to go about it, considering I would have to allocate twice the memory occupied by the array itself in order to create enough stack space for a worst-case scenarion, not to mention that would require stdlib.h, and I'm trying to avoid using libraries if possible. However, I am concerned that, using recursion, this function could possibly overload the execution stack and collapse the universe into a singularity.

Anyway, I'm open to criticism, be it constructive or purely vitriolic. Thanks!

Code:void __qs_sw(int* a, int* b) { int s = *a; *a = *b; *b = s; } // quicksort(int* arr, unsigned nm) // int* arr: the pointer to the beginning of your array // int nm: the number of members in your array // // example: // int arr[] = { 33, -33, 2124, 99, -1000, 40, 27, 99, 30 }; // quicksort(arr, sizeof(arr) / sizeof(int)); extern void quicksort(int* arr, unsigned nm) { int lp=1, rp = nm - 1; // initialize the pointers at the left and right sides of the array while (lp < rp) // loop until the pointers collide if (arr[lp] > arr[0] && arr[rp] < arr[0]) // if the left side is greater and the right side is lesser, __qs_sw(&arr[lp++], &arr[rp--]); // swap the values else if (arr[lp] <= arr[0]) // otherwise, if the left side is greater lp++; // increment the left pointer else // otherwise, if the right side is lesser rp--; // decrement the right side pointer if (arr[lp] > arr[0]) // now, compare the last value the left pointer is sitting on to the pivot lp--; // if it's greater than the pivot, decrement lp (which is now the target to swap the pivot into) __qs_sw(&arr[lp], &arr[0]); // now, swap the pivot into its new target home if (lp > 1) // if we have more than one left-side member, quicksort(arr, lp); // sort the left-side sub-array if (nm - lp > 2) // if we have more than one right-side member, quicksort(&arr[lp + 1], nm - lp - 1); // sort the right-side sub-array }