CODEWITHSUNDEEP
c++algorithm
bjackfly
bjackfly

Reputation: 3336

Using std::partition with Quick Sort

What's wrong with the quickSort method using partition below? Nth element seems to work fine but I thought partition would also work. I saw an example that had 2 partition calls but shouldn't I just need one?

#include <iostream>
#include <algorithm>
#include <iterator>

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

  auto midIt = lowerIt + d / 2;

  std::nth_element ( lowerIt, midIt, upperIt);

  quickSortWorks( lowerIt, midIt );
  quickSortWorks( midIt+1, upperIt );
}


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

  auto midIt = lowerIt + d / 2;

  auto pIt = std::partition ( lowerIt, upperIt, [midIt](int i) { return i < *midIt; } );

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

int main ( )
{
  unsigned int N = 10;
  std::vector<int> v(N);
  // srand (time(nullptr));
  for_each(v.begin(), v.end(), [](int& cur){ cur = rand()%100; });

  std::vector<int> vorig(v);

  auto print_vec = [](std::ostream& out, const std::vector<int>& v) {
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(out, ", "));
    out << std::endl;
  };

  std::cout << " Using Partition: " << std::endl;
  std::cout << " Before: " << std::endl;
  print_vec(std::cout,v);
  quickSort(v.begin(), v.end());
  std::cout << " After: " << std::endl;
  print_vec(std::cout,v);

  v = vorig;
  std::cout << " Using Nth Element: " << std::endl;
  std::cout << " Before: " << std::endl;
  print_vec(std::cout,v);
  quickSortWorks(v.begin(), v.end());
  std::cout << " After: " << std::endl;
  print_vec(std::cout,v);
}

Output:

Using Partition: 
 Before: 
83, 86, 77, 15, 93, 35, 86, 92, 49, 21, 
 After: 
21, 15, 77, 35, 49, 83, 86, 92, 86, 93, 

Using Nth Element: 
 Before: 
83, 86, 77, 15, 93, 35, 86, 92, 49, 21, 
 After: 
15, 21, 35, 49, 77, 83, 86, 86, 92, 93,

Upvotes: 2

Views: 3366

Answers (4)

Vaibhav Agnihotri
Vaibhav Agnihotri

Reputation: 11

I just gone through the same problem. After spending hours on analyzing, at last I came to the solution, Voila!!

As already mentioned std::partition with proposed predicate will segregate the array in two parts, first part consists of elements less than pivot and second part, elements greater than or equal to the pivot. But it is not guaranteed that pivot will be the first element in the second part.

Well, std::stable_partition does the job. Just take the pivot as first element and apply the stable_partition. Since it will maintain the order of occurrence while partitioning. It is now guaranteed that pivot will be the first element in second part.

PS: Don't get confused with two parts. I used the term to explain things more clearly.

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

  auto pIt = lowerIt;

  auto pValue = *pIt; 

  pIt = std::stable_partition ( lowerIt, upperIt, [pValue](int i) { return i < pValue; } );

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

Upvotes: 1

Johnny Cage
Johnny Cage

Reputation: 81

The code as written only works accidentally and here's why,

std::partition does its job by predicate, the forward sequence contains elements that evaluate to true, the remainder evaluate to false. This means that std::partition views elements that are greater than the pivot and elements that are equal to the pivot as equivalent.

There is no guarantee on ordering for the sequence [middle,last)!

Obviously this is not what you want. You would like to compact elements equal to pivot to the front of the sequence [middle,last). This is why the example code you had looked at used a second partition, to impose this ordering on the trailing sequence (minimally you'll need the pivot element in correct position).

For the sake of clarity,

template<typename Ran>
  void quicksort(Ran first, Ran last)
  {
    typedef typename std::iterator_traits<Ran>::value_type value_type;
    if (last - first < 2)
       return;
    Ran middle = first + (last - first)/2;
    // save pivot.
    std::iter_swap(middle, last-1);
    middle = std::partition(first, last-1,
        [last] (const value_type& x) { return x < *(last-1); });
    // restore pivot.
    std::iter_swap(middle, last-1);
    quicksort(first, middle);
    quicksort(middle+1, last);
  }

Upvotes: 8

arayq2
arayq2

Reputation: 2554

It won't work, even with the lambda fix, because std::partition, unlike std::nth_element, doesn't return an iterator suitable for the divide-and-conquer recursion.

The return value of a call to std::partition is the iterator to the first value in the "upper" range of the partition, where the predicate has failed. Except by accident, this will not be an iterator to the "smallest" in that range.

By contrast, the "pivoting" operation in std::nth_element achieves exactly that, which is also necessary for the bifurcating recursion.

The failure can be seen by working the example by hand for just the first iteration. With this test sequence of 10 elements:

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

The first "pivot" will be the 6th element (at index 0 + 10/2 = 5), i.e. 35. Using the criterion "less than 35" std::partition will rearrange the array at the first step to

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

and return a pointer to the 3rd element (=77). It should be obvious that the value 77 will remain at that third position for the duration of the algorithm. And this is clearly wrong.

Upvotes: 5

Camille
Camille

Reputation: 1690

Your closure should capture the value of *midIt, rather than midIt: the quantity "*midIt" will change during partitioning.

int midValue = *midIt;
std::partition(lowerIt, upperIt, [midValue](int i)...

Upvotes: 0

Related Questions