Quicksort 3 way partition too slow

Question

I am using quicksort 3 way partition, but it is turning out to be too slow as and when the vector size is greater than 10000. What am I doing wrong? Please guide me! Any help will be appreciated The answer should be computed in less than 2.2 sec.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>

using std::vector;
using std::swap;

void print(vector<int> v)
{
  for(int i = 0; i < v.size(); i++) std::cout << v[i] << " ";
  std::cout << std::endl;
}

void partition2(vector<int> &a, int l, int r, int &i, int &j) {
  int k;
  int middle=(l+r)/2;
  /*Selecting pivot as median of low, high and middle*/
  if(((a[l]<=a[middle]) && (a[middle]<=a[r])) || ((a[r]<=a[middle]) && (a[middle]<=a[l])))
      k=middle;
  else if(((a[middle]<=a[l]) && (a[l]<=a[r])) || ((a[r]<=a[l]) && (a[l]<=a[middle])))
      k=l;
  else if(((a[middle]<=a[r]) && (a[r]<=a[l])) || ((a[l]<=a[r]) && (a[r]<=a[middle])))
      k=r;

  swap(a[l], a[k]);
  //print(a);

  int low_value = a[l];
  int index_low = l;
  int index_high = l;
  int counter=l;
  for (int i = l + 1; i <= r; i++) {
    if (a[i] < low_value) {
      swap(a[i], a[index_low]);
      counter++;
      low_value=a[l];
    }
    else if(a[i]==low_value)
    {
        index_high++;
        swap(a[i], a[index_high]);      
    }
    //print(a);
  }

  i=counter;
  j=index_high;
  //swap(a[l], a[j]);
  //return j;
}

void randomized_quick_sort(vector<int> &a, int l, int r) {
  if (l >= r) {
    return;
  }

  int i,j;
  partition2(a, l, r, i, j);

  randomized_quick_sort(a, l, i-1);
  randomized_quick_sort(a, j+1, r);
}

int main() {
  int n;
  std::cin >> n;
  //while(1){
  //n=100+rand()%99999;
  //std::cout<<n<<std::endl;
  vector<int> a(n);
  for (size_t i = 0; i < a.size(); ++i) {
    std::cin >> a[i];
    //a[i]=1+rand()%99999999;
  }
  randomized_quick_sort(a, 0, a.size() - 1);
  for (size_t i = 0; i < a.size(); ++i) {
    std::cout << a[i] << ' ';
  }
  //std::cout<<"Pass\n";  
  //}
  return 0;
}

how do you benchmark? are you sure that the randomized_quick_sort call in main takes 2.2 seconds when input size > 10000? Or the whole program takes 2.2 seconds? And did you compile with flags like -O2? — Petar Petrovic, Apr 24 '17 at 08:24
@PetarPetrovic the time difference is quite visible when the input size is between 10000 and 100000. I test it on Coursera's own platform where they indicate the time. And yes, i am compiling with -O2 flags — darkfall94, Apr 24 '17 at 08:30
I suspect the problem is the partition2(). I add following code the see the pivot position partition2(a, l, r, i, j); if (r - l > 1000){ std::cout << l << ' ' << r << ' ' << i << ' ' << j << '\n'; } and see result like 1436 2599 1437 1436, 1437 2599 1438 1437, it means the pivot does not divide the array evenly and I guess this should not be true all the time Input is generated by python random within some range and default seed. — Petar Petrovic, Apr 24 '17 at 09:06

score 0 · Answer 1 · answered Apr 24 '17 at 08:29

Everything at first glance is correct. However, there are probably just too many comparison operations. Try this option - it works on my computer for 1.6 seconds on average.

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <ctime>
#include <random>
#include <chrono>
#include <iomanip>

using namespace std;
using namespace std::chrono;

//======= quick_sort =======//
template<typename T>
int partition(vector<T>& numbers, const int& left, const int& right)
{
    swap(numbers[left], numbers[left + (right - left) / 2]);
    T mid = numbers[left];
    int i(left + 1), j(right);

    while (i <= j)
    {
        while ( i <= j && numbers[i] <= mid ) i++;
        while ( i <= j && numbers[j] > mid ) j--;
        if ( i < j ) swap(numbers[i], numbers[j]);
    }

    swap(numbers[i - 1], numbers[left]);
    return i - 1;
}

template<typename T>
void quick_sort_rec(vector<T>& numbers, const int& left, const int& right)
{
    if (left >= right) return;

    int p = partition(numbers, left, right);
    quick_sort_rec(numbers, left , p - 1);
    quick_sort_rec(numbers, p + 1 , right);
}
//=========================//


template<typename T>
T random_T(long min, long max)
{
    return (T)min + static_cast<T>(rand()) / (static_cast<T>(RAND_MAX / ((T)(max - min))));
}

template<typename T>
float time_func(void (*f)(vector<T>&, const int&, const int&), vector<T>& a)
{
    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    f(a, 0, a.size() - 1);
    high_resolution_clock::time_point t2 = high_resolution_clock::now();

    return 1000.0 * (duration_cast<microseconds>(t2 - t1).count()) / (float)(CLOCKS_PER_SEC); /// CLOCKS_PER_SEC;
}

int main()
{
    srand((unsigned)(777));
    vector<int> a;

    for (int i = 0; i < 10000; i++)
    {
        a.push_back(random_T<int>(0, 1000));
    }

    cout << setprecision(10) << "quick sort rec = " << time_func(quick_sort_rec, a) << endl;
    return 0;
}

Thanks for your code, but it would be more helpful if I knew where I am consuming so much time and how to reduce it rather than just copying your solution. — darkfall94, Apr 24 '17 at 08:35
As I said that the bottleneck is your way to choose pivot element in the array. Quicksort quality significantly depends on this moment. However - you always can implement sorting without recursion, it may allows to slightly reduce time. See [this](http://stackoverflow.com/questions/12220546/quicksort-optimizations) question, for example, for more info. — Igor Poletaev, Apr 24 '17 at 08:44
P.S.: The desire to reduce the time to the Nlog_{3}(N) unfortunately faces additional overhead. And most likely to implement sorting with three subarrays much faster than with two - will not work. At least it will not be easy. So here it is necessary to think - you want incredible optimization or reliability. — Igor Poletaev, Apr 24 '17 at 08:55

Petar Petrovic · Answer 2 · 2017-04-25T02:33:03.740

0

I run the following code to test partition2

int main(){
    vector<int> a = {2, 1, 1, 9, 5, 3, 4, 2, 7};
    int i, j;
    partition2(a, 0, a.size() - 1, i, j);
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
    return 0;
}

And the results are

1 1 5 9 2 3 4 2 7

If the partition2 selecting median of low, high and middle as pivot, then the pivot should be 5 and the results should be something like

2 1 1 3 4 2 5 9 7

Then I check the code

if (a[i] < low_value) {
  swap(a[i], a[index_low]);
  counter++;
  low_value=a[l];
}
else if(a[i]==low_value)
{
    index_high++;
    swap(a[i], a[index_high]);      
}

It seems to be that the code try to find the minimum value of array and then move them to beginning of array. It seems that it is doing selection sort instead of quicksort. It explains why it is slow when input size is large.

edited Apr 25 '17 at 02:33

answered Apr 24 '17 at 09:28

Petar Petrovic

404
3
6

I am not sure which code you ran, but my code runs perfectly fine and displays correct results. If you uncomment the print statements, here is what you get: 1 1 2 2 3 4 5 7 9 and even the pivot is correct i.e. 5. As far as this "It seems to be that the code try to find the minimum value of array and then move them to beginning of array." is concerned, the data set reduces to half each time after partitioning – darkfall94 Apr 24 '17 at 15:40
@darkfall94 I updated my ans. Basically I just called partition2 once in main to test this function. Do you have same result if you just copy my main and run it? – Petar Petrovic Apr 25 '17 at 02:36

Quicksort 3 way partition too slow

2 Answers2