QuickSort method using only a single vector as input parameter in C++

Question

I am attempting to write a QuickSort method in C++. I think my issue is with:

if( i <= j )

Because this is not comparing the values in the vector but my index. I attempted to use the brackets operator [] to access the value but then the code consumes memory and doesn't end on its own.

Also i would prefer to keep it a single method instead of splitting it into a method to partition and a method to sort.

STD::sort is implemented elsewhere along with other sort methods. I am just having trouble writing this one; and my input is restricted to a vector.

This is what i have

vector<double> QuickSort(vector<double> & vec1){

    double i = 0;
    double j = vec1.size()-1;
    int size = vec1.size();
    double tmp;

    double pivot = vec1[(i + j) / 2];

//   partition 

    while (i <= j) {
        while (vec1[i] < pivot)
            i++;
        while (vec1[j] > pivot)
            j--;
        if (vec1[j] <= vec1[j-1]) {
            tmp = vec1[j-1];
            vec1[j-1] = vec1[j];
            vec1[j] = tmp;
            i++;
            j--;
        }
    }

//    recursion 

    if (vec1[i] > vec1[i+1]) {
        QuickSort(vec1);
    }

    if (vec1[j] <vec1[j-1]) {
        QuickSort(vec1);
    }

    return vec1;
}

Suggestions and advice please.

ive seen a number of implementations that utilize three inputs. I am attempting to reduce that to one... a vector. — William Machado, Mar 29 '18 at 07:51
would not splitting it up to multiple functions resolve your problem ? just call the qsort with one parameter and internally call other implementation functions. — Samer Tufail, Mar 29 '18 at 08:04

Junhee Shin · Answer 1 · 2018-03-29T08:37:43.817

I modified your code like this. I decided pivot index as last item. and added some test code. it worked normally. I think that if QuickSort function has from, to index parameters, can be implemented more simply.

#include <iostream>
#include <vector>
#include <chrono>


using namespace std ;

void printvector(vector<double> v) {
cout << "vector : " ;
for (double n : v) {
cout << n << " " ;
}
cout << endl ;
}

vector<double> QuickSort(vector<double>& vec1){

    double i = 0;
    double j = vec1.size()-2;
    double tmp;
    int pivotindex = vec1.size()-1 ;
    double pivot = vec1[pivotindex];

    if ( vec1.size()<=1 )
        return vec1 ;

    cout << "QuickSort: ";
    printvector(vec1) ;

    while (i <= j) {
        while (vec1[i] < pivot) {
            i++;
        }
        while (vec1[j] > pivot)
            j--;
         if (i <= j) {
            tmp = vec1[i];
            vec1[i] = vec1[j];
            vec1[j] = tmp;
            i++;
            j--;
        }
    }
    // pivot change
    vec1[pivotindex] = vec1[i] ;
    vec1[i]=pivot ;
    pivotindex=i ;

    cout << "pivotting: ";
    printvector(vec1) ;

    if (vec1.size()<=2 )
        return vec1 ;
    // partition
    vector<double> left_vec, right_vec ;
    vector<double>::iterator pivotiter = vec1.begin()+pivotindex ;
    copy(vec1.begin(), pivotiter, back_inserter(left_vec)) ;
    copy(pivotiter+1, vec1.end(), back_inserter(right_vec)) ;

    cout << "left: ";
    printvector(left_vec) ;
    cout << "right: ";
    printvector(right_vec) ;

   if (left_vec.size()>0 ) {
        QuickSort(left_vec);
        copy(left_vec.begin(), left_vec.end(), vec1.begin()) ;
    }
   if (right_vec.size()>0 ) {
        QuickSort(right_vec);
        copy(right_vec.begin(), right_vec.end(), pivotiter+1) ;
    }
    return vec1;
}

int main()
{
//vector<double> v { 5 } ;
//vector<double> v { 5, 3 } ;
//vector<double> v { 5, 3, 1 } ;
//vector<double> v { 1, 3, 5 } ;
//vector<double> v { 9,4,8,5,1,2,7 } ;
vector<double> v  ;
//srand( time(NULL) ) ;
int64_t now = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count();
srand( now ) ;
for (int i=0; i<rand()%30+1; i++) {
    v.push_back( rand()%10000 ) ;
}

cout << "input values: " ;
printvector(v) ;

vector<double> ret = QuickSort(v) ;
cout << "output values: " ;
printvector(ret) ;
cout << endl << endl ;

return 0 ;
}

output is this.

input values: vector : 1778 9400 9330 783 3148 2029 9685 
QuickSort: vector : 1778 9400 9330 783 3148 2029 9685 
pivotting: vector : 1778 9400 9330 783 3148 2029 9685 
left: vector : 1778 9400 9330 783 3148 2029 
right: vector : 
QuickSort: vector : 1778 9400 9330 783 3148 2029 
pivotting: vector : 1778 783 2029 9400 3148 9330 
left: vector : 1778 783 
right: vector : 9400 3148 9330 
QuickSort: vector : 1778 783 
pivotting: vector : 783 1778 
QuickSort: vector : 9400 3148 9330 
pivotting: vector : 3148 9330 9400 
left: vector : 3148 
right: vector : 9400 
output values: vector : 783 1778 2029 3148 9330 9400 9685

Caleth · Accepted Answer · 2018-03-29T09:08:18.303

The first rule of writing a recursive function is to define the case where there is nothing left to do. Your code does not do this, and assumes it is never reached. A vector with a size <= 1 is vacuously sorted, and testing vec1[i] > vec1[i+1] on such a vector is undefined behaviour.

The second rule of writing a recursive function is to make sure that you are reducing your problem size with each inner invocation. Your code does not do this, it passes the whole vector to itself (twice, if the first would ever return).

Vectors are not indexed by doubles, but by size_ts (or ints with a sign conversion).

You are accepting vec1 by reference, mutating it, then copying it in the return. Do one of those, not both.

Implementation from here

namespace detail {    
    template<class FwdIt, class Compare = std::less<>>
    void QuickSortImpl(FwdIt first, FwdIt last, Compare cmp = Compare{})
    {
        auto const N = std::distance(first, last);
        if (N <= 1) return;
        auto const pivot = *std::next(first, N / 2);
        auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
            return cmp(elem, pivot); 
        });
        auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
            return !cmp(pivot, elem);
        });
        QuickSortImpl(first, middle1, cmp);
        QuickSortImpl(middle2, last, cmp);
    }   
}

void QuickSort(vector<double>& vec1)
{
    detail::QuickSortImpl(vec1.begin(), vec1.end());
}

If you really insist on having one function parameter, it can be done with a range library (boost::range or range v3)

template<class Range>
void QuickSort(Range& range)
{
    auto const N = std::distance(range.begin(), range.end());
    if (N <= 1) return;
    auto const pivot = *std::next(range.begin(), N / 2);
    auto left_range = boost::partition<boost::return_begin_found>(
        range.begin(), 
        range.end(), 
        [=](auto const& elem){ 
            return elem < pivot; 
        }
    );
    auto right_range = boost::partition<boost::return_found_end>(
        left_range.end(), 
        range.end(), 
        [=](auto const& elem){ 
            return !(pivot < elem);
        }
    );
    QuickSort(left_range);
    QuickSort(right_range);
}

First off, thank you. Second, holy crap. I will seek to attain your knowledge base and skills. cuz wow. thats some elegant code. — William Machado, Mar 29 '18 at 18:29

schorsch312 · Answer 3 · 2018-03-29T07:56:40.300

I suggest to use std::sort unless you have a very good reason not to do so.

In order to have a function taking only one parameter, a wrapper of std::sort may look like this, but you are copying your vector. If you do not like this you can pass it by reference.

#include <iostream>   // std::cout
#include <algorithm>  // std::sort
#include <vector>     // std::vector

std::vector<double> mySort(const std::vector<double> unsorted) {
    std::vector<double> sorted = unsorted; 
    std::sort(sorted.begin(), sorted.end()); 
    return sorted;
}

int main() {
    std::vector<double> myvector{32, 71, 12, 45, 26, 80, 53, 33};

    for (const auto item : myvector) {
        std::cout << item << " ";
    }
    std::cout << std::endl;

    auto myvector_sorted = mySort(myvector);

    for (const auto item : myvector_sorted) {
        std::cout << item << " ";
    }
    std::cout << std::endl;

    return 0;
}

Nevertheless, the bottom of your implementation is not meaningful, since

if (vec1[i] > vec1[i + 1]) {
    QuickSort(vec1);
}
if (vec1[j] < vec1[j - 1]) {
    QuickSort(vec1);
}

will always start QuickSort with vec1. You need to pass i and j as well. In order to have one parameter interface you can write

vector<double> QuickSort(vector<double> & vec1, int i = 0, int j = vec1.size() - 1 ) {
    int size = vec1.size();
    ....

I am using sort in another section of the project to show its complexity(big O) in comparison. I Have implemented a bubblesort, insertsort, and a selection sort that all work properly, i am just having issues getting this one working. — William Machado, Mar 29 '18 at 07:48

QuickSort method using only a single vector as input parameter in C++

3 Answers3