non recursive quick sort in c++

Question

I'm relatively new to c++ programming. I have a few years of experience writing simple Arduino programs, but I always kept to the basics. I also have some more experience with Python.

I set myself the challenge of writing a non-recursive quick sort algorithm. I'm wondering if anyone has feedback on style, best practices, or things that could be more efficient.

The relevant function is void quickSortNonRec but I left the minimum functions in the file to show testing.

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

// Takes two pointers and switches the values they point to.
void flip(int* p, int* q) {
    if(p!=q){           // Don't do anything if p and q point to the same place already. This check might be more expensive than just doing the operation anyway.
        int tmp = *p;   // One placeholder is needed to flip values.
        *p = *q;
        *q = tmp;
    }
}


typedef tuple<int*,int*> addrRange;       //Shorthand for tuple pointing to address range

// Implementation of a non-recursive quicksort algorithm.
// All values between and including start and stop will be sorted in place.
// The ranges left to be sorted are kept track of by a vector of 2-tuples of pointers.
void quickSortNonRec(int* start, int* stop) {
    vector<addrRange> startStopPairs;            // Stack of start/stop pairs
    startStopPairs.push_back(make_tuple(start,stop));   // First pair is the whole array
    while (int N = startStopPairs.size()) {             // Check if any ranges are left to be sorted
        addrRange pair = startStopPairs[N-1];           // Get the last start stop pair
        startStopPairs.pop_back();                      // Pop last pair from the stack
        int* tmpStart = get<0>(pair);                   // Put in seperate pointers
        int* tmpStop  = get<1>(pair);                   // "
        int* p = tmpStart;                              // p points to the 'middle' element (see loop invariant)
        
        // LOOP INVARIANTS: (These should be true at the end of each loop)
        // (*tmpStart is the pivot element)
            // For all j where (tmpStart < j<=p) : *j< *tmpStart
            // For all j where (p < j < i)       : *j>=*tmpStart
        for (int* i = p+1; i <= tmpStop; ++i) {     // Loop over the whole array
            if (*i < *tmpStart) {                   // Check if the current value is under the pivot
                flip(i,++p);                        // If so, increase p and flip *i with *p 
            }
        }
        flip(tmpStart,p); // Wedge the pivot in the middle.
        // Now all values before the pivot are smaller than the pivot. All values after the pivot
        // are at least as big as the pivot. Thus the pivot is in the right place.
        
        // Add ranges that should still be sorted. (Size of range exceeds 1)
        if (p-1 > tmpStart) {startStopPairs.push_back(make_tuple(tmpStart,p-1));}
        if (tmpStop > p+1 ) {startStopPairs.push_back(make_tuple(p+1,tmpStop ));}
    }
}

void printRange(int* start, int* stop) {
    for (int* i = start; i <= stop; ++i){
        cout << *i << " ";
    }
    cout << "\n";
}

int main()
{   
    const int arSize = 10;
    int ar[arSize] = {6,43,7,3,6,3,5,4,6,3};
    printRange(ar,ar+arSize-1);
    quickSortNonRec(ar,ar+arSize-1);
    printRange(ar,ar+arSize-1);
    return 0;
}

```

Answer 1

First of all, the code looks correct. Kudos.

Few notes though.

• No naked loops. Every loop implements an important algorithm, and therefore deserves a name. In your case, the loop

    for (int* i = p+1; i <= tmpStop; ++i)
  

  partitions the range. Lift it into a partition function. Not only it will make the code more readable, but also more testable. Now you can unit test partition. And more maintainable too: you may change the partitioning strategy and not touch the core of sorting.

• Most range algorithms are more naturally expressed in terms of a semi-open range (that is, the end does not belong to the range, but is one-beyond). With such contract you don't need to -1 anywhere, and you may use < instead of <=.

• I am not sure that std::vector is the best choice to represent the stack. STL conveniently offers a stack container.

• flip is likely inferior to std::swap.

• Stop using namespace std. It is a bad habit.