std::partition quick sort implementation [closed]

Question

I thought my implementation below was working but apparently not. Any ideas on what is wrong with this quick sort implementation using std::partition? I have a version using nth_element version that works that has very similar and simpler code than this.

template <typename It>
void quickSort (const It& lowerIt, const It& upperIt)
{
  auto d = upperIt  - lowerIt ;
  if ( d < 2 )
   return;

  auto midIt = lowerIt + d / 2;

  using T = typename std::iterator_traits<It>::value_type;

  T midValue = *midIt;

  auto pIt = std::partition ( lowerIt, upperIt, [midValue](T i) { return i < midValue; } );

  quickSort( lowerIt, pIt );
  quickSort( pIt + 1, upperIt );
}

Using Partition:

Before:

83, 86, 77, 15, 93, 35, 86, 92, 49, 21,

After:

21, 15, 77, 35, 49, 83, 86, 92, 86, 93,

Answer 1

It is not guaranteed, that the pivot element will be at location pIt. In most cases it will not. So, you should change your algorithm as follows:

• choose a pivot element
• swap the pivot element with *std::prev(upperIt)
• use std::partition on the range [lowerIt, std::prev(upperIt))
• swap pIt with *std::prev(upperIt)
• call quick-sort recursively as in you code

Here is a fixed version of your code:

template <typename It>
void quickSort(It lowerIt, It upperIt)
{
    using std::swap;
    auto size = std::distance(lowerIt, upperIt);
    if (size > 1) {
        auto p = std::prev(upperIt);
        swap(*std::next(lowerIt, size / 2), *p);
        auto q = std::partition(lowerIt, p, [p](decltype(*p) v) { return v < *p; });
        swap(*q, *p);
        quickSort(lowerIt, q);
        quickSort(std::next(q), upperIt);
    }
}

Answer 2

Your code has a couple of serious problems. Let's consider them individually.

First, if the item you pick as the pivot happens to be the smallest in the collection, you'll get infinite recursion -- it'll put all the elements into the upper partition, but when it attempts to sort the upper partition, it'll get the same elements in the same order, put them all in the upper partition and repeat indefinitely.

The most common way to eliminate this is to use a median of three pivot selection. This (nearly) guarantees that there will be at least one item smaller than the pivot and one item larger than the pivot, so even in the worst case you'll put at least one item in each partition. The sole exception is if the three items you choose are all identical (in which case you generally need/want to re-choose your pivot value).

Second, like almost everything that uses iterators, std::partition assumes a half-open range -- i.e., that the first iterator points at the beginning of the range, and the second iterator points just past the end of the range. This means you want your recursive calls to be:

quicksort(lowerIt, pIt);
quicksort(pIt, upperIt);

In theory, skipping the pivot element doesn't actually hurt anything (and can be used to prevent the previous problem) but leaving an item out of the processing when you recurse is sufficiently unusual that I'd generally avoid it. For this to work as a way of avoiding infinite recursion, you have to swap your pivot to the first spot in the upper partition, so it's the one you're leaving out of what you pass in your recursive calls. If you leave out some other element, you're going to run into problems because you won't sort all the elements.

For a "serious" implementation of Quicksort there are a few other details you probably want to change as well, such as stopping recursion when your partition size gets down to something like 20 items, then when you're done that way, do an insertion sort over the entire collection to get everything to its final resting place (so to speak).

Likewise, to avoid stack overflow, you normally want to sort the smaller of the two partitions first. This ensures stack space will never exceed O(log N). As it currently stands, stack space can be O(N) worst case.