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
}