3
\$\begingroup\$

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 tag too.

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

\$\endgroup\$
3
  • \$\begingroup\$ with C++ I prefer std::vector instead of raw array \$\endgroup\$
    – Garf365
    Feb 25 '16 at 13:26
  • \$\begingroup\$ Good approach @Garf365, but I had a reason, see my edit. \$\endgroup\$
    – gsamaras
    Feb 25 '16 at 16:00
  • 1
    \$\begingroup\$ @gsamars Ok, so nothing to say anymore ;) \$\endgroup\$
    – Garf365
    Feb 25 '16 at 16:08
2
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ Note that as a general purpose swap method, void swapNoTemp(int& a, int& b) fails with int x = 5; swapNoTemp(x, x) --> x is now 0. \$\endgroup\$ Feb 25 '16 at 16:40
  • \$\begingroup\$ 1) Good, but where to put the others? Only one file here. 2) Won't static confuse the beginner? 3) Perfect, you just got an upvote for this. 4) Too much for an introduction to Quicksort. 5) Very good idea! 6) Agreed, wonder why I had that as is..Wrote the code some years ago. 7) It will work as is, because of the equality, I think, good catch though. 8) You mean no explanation in the pseudosite? Yes I know it will fail, probably it would the time I found out that we could do the swap like this and I used it to impress the girls on the class ( kidding :) ) \$\endgroup\$
    – gsamaras
    Feb 25 '16 at 16:49
  • \$\begingroup\$ @gsamaras 1) Put sort functions in top half of code, put test code in the bottom half with long ////////// between. 2) By the time a learner is looking into implementations of sort functions, I would expect them to also understand static. swapNoTemp() --> wonder if it had a positive Darwinian effect? \$\endgroup\$ Feb 25 '16 at 17:04
  • \$\begingroup\$ @gsamaras Concerning the > vs. >= usage: This is the beginning of discussing stability of a sort. With an int array, it is hard to demo this concern, but had the elements been strings and the compare was strcasecmp(), we could take a pre-sorted array and see if it comes up the same. \$\endgroup\$ Feb 25 '16 at 17:12
  • 1
    \$\begingroup\$ I will keep that a secret for now...so that I can post it when Stack opens a site for Love etc. :P \$\endgroup\$
    – gsamaras
    Feb 25 '16 at 17:20
1
\$\begingroup\$

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
   }
}
\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.