Quicksort for a pseudosite

Question

I have a pseudosite, where I actually post small functions, so that I can re-use them^*, but some posts have visitors. The top is Quicksort (C++). I feel that beginners visit it, so I do not care in improving (its poor) performance, but only the readability, so that the beginner can catch things more easily.

#include <iostream>

void quickSort(int a[], int first, int last);
int pivot(int a[], int first, int last);
void swap(int& a, int& b);
void swapNoTemp(int& a, int& b);
void print(int array[], const int& N);

using namespace std;

int main()
{
    int test[] = { 7, -13, 1, 3, 10, 5, 2, 4 };
    int N = sizeof(test)/sizeof(int);

    cout << "Size of test array :"  << N << endl;

    cout << "Before sorting : " << endl;
    print(test, N);

    quickSort(test, 0, N-1);

    cout << endl << endl << "After sorting : " << endl;
    print(test, N);

    return 0;
}

/**
 * Quicksort.
 * @param a - The array to be sorted.
 * @param first - The start of the sequence to be sorted.
 * @param last - The end of the sequence to be sorted.
*/
void quickSort( int a[], int first, int last ) 
{
    int pivotElement;

    if(first < last)
    {
        pivotElement = pivot(a, first, last);
        quickSort(a, first, pivotElement-1);
        quickSort(a, pivotElement+1, last);
    }
}

/**
 * Find and return the index of pivot element.
 * @param a - The array.
 * @param first - The start of the sequence.
 * @param last - The end of the sequence.
 * @return - the pivot element
*/
int pivot(int a[], int first, int last) 
{
    int  p = first;
    int pivotElement = a[first];

    for(int i = first+1 ; i <= last ; i++)
    {
        /* If you want to sort the list in the other order, change "<=" to ">" */
        if(a[i] <= pivotElement)
        {
            p++;
            swap(a[i], a[p]);
        }
    }

    swap(a[p], a[first]);

    return p;
}


/**
 * Swap the parameters.
 * @param a - The first parameter.
 * @param b - The second parameter.
*/
void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}

/**
 * Swap the parameters without a temp variable.
 * Warning! Prone to overflow/underflow.
 * @param a - The first parameter.
 * @param b - The second parameter.
*/
void swapNoTemp(int& a, int& b)
{
    a -= b;
    b += a;// b gets the original value of a
    a = (b - a);// a gets the original value of b
}

/**
 * Print an array.
 * @param a - The array.
 * @param N - The size of the array.
*/
void print(int a[], const int& N)
{
    for(int i = 0 ; i < N ; i++)
        cout << "array[" << i << "] = " << a[i] << endl;
} 

As you see, I use many things from C, since I wanted the code to be able to work in a C program with minor modifications, thus I am adding c tag too.

*_{since I find it easier to find them there than in my FS and it helps in restoring harmony after a nuke.}

Answer 1

Only small/minor issues:

1. Since code it to be portable to C with minor mods, suggest demarcating that which is sort code from test code. Its appears the sort code is only these 3. Do not mix test code with the application code. Better in separate files.

   void quickSort( int a[], int first, int last ) 
   int pivot(int a[], int first, int last) 
   void swap(int& a, int& b)
   

2. pivot(), swap() should be static functions. No need for them outside this file.

3. Minor: int vs. size_t. An int index may lack sufficient range to index an array. Use size_t as that is Goldilocks type neither to narrow nor wide a type to handle all array sizes - it is just right. As size_t is some unsigned type, watch out for attempting to create negative values. I did not notice any issue for your code concerning that.

   // int N = sizeof(test)/sizeof(int);
   size_t N = sizeof(test)/sizeof(int);
   
   // void quickSort( int a[], int first, int last )
   void quickSort( int a[], size_t first, size_t last )
   
   // int pivot(int a[], int first, int last) 
   size_t pivot(int a[], size_t first, size_t last) 
   

4. The sort would works well with other types beside int. Perhaps code that way.

   typedef int sort_type;     
   void quickSort(sort_type a[], size_t first, size_t last ) 
   

5. Function signature: Rather than oblige the calling code to supply 0, n-1, create a top level call:

   void quickSortTop(sort_type a[], size_t size) {
     if (size) quickSort(a, 0, size-1);
   }
   

6. Minor: Keep local variables as local as able. pivotElement could be declared and initialized in 1 step local to the if() block as it is not used outside the block. This borders on style issues, but as a rule, limiting variable scope is easier to see its use and impact.

   int pivotElement;  // here 
   if(first < last) {
       int pivotElement = pivot(a, first, last); // or here
       quickSort(a, first, pivotElement-1);
       quickSort(a, pivotElement+1, last);
   }
   

7. Minor: Correct comment? I would think to reverse the order a >= would be needed. If this is not so, then I would expect < to work slightly faster than <=.

   /* If you want to sort the list in the other order, change "<=" to ">" */
   /* If you want to sort the list in the other order, change "<=" to ">=" */
   

8. Minor: Dead code swapNoTemp(). No explanation for its existance here.

Answer 2

As pointed out by @chux in a comment, swapNoTemp is a problem if used with:

int x = 5;
swapNoTemp(x, x); // x will be set to 0.

To address that problem, you can add a check that makes sure that such cases become noops.

void swapNoTemp(int& a, int& b)
{
   if ( &a != &b )
   {
      a -= b;
      b += a;// b gets the original value of a
      a = (b - a);// a gets the original value of b
   }
}