How do I use C++ library algorithms partition function to quicksort?

Question

I am trying to perform quicksort using C++ library partition function, Here's my code

int p;
int pred(int x)
{
    return x<=p;
}

    void quickSort(vector<int>::iterator first,vector<int>::iterator last) {
    if(first == last)
        return;
    if((first+1) == last)
        return;
    p = *first;
    auto mid = partition(first,last,pred);
    quickSort(first,mid);
    quickSort(mid,last);
    --mid;
    swap(*mid,*first);
    for(auto itr = first;itr!=last;++itr)
        cout<<(*itr)<<" ";
    cout<<endl;
}

It gives segFault in the partition function. I want to use the library function.

you know that another C++ library algorithm implements quicksort, right? — Stack Overflow is garbage
– Stack Overflow is garbage, Commented Jan 8, 2014 at 9:45

Ezra · Accepted Answer · 2014-01-08 11:25:46Z

1

This one uses lambda:

void quick(std::vector<int>::iterator first, std::vector<int>::iterator last)
{
    if (first == last) return;

    auto pivot = *first;
    auto mid = std::partition(first, last, [pivot](int i){return pivot > i;});
    if (mid == last) return;
    quick(first, mid);
    quick(++mid, last);
}

edited Jan 8, 2014 at 11:25

answered Jan 8, 2014 at 9:26

Ezra

1,5035 gold badges16 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

doptimusprime · Accepted Answer · 2014-01-08 09:16:48Z

1

bool pred(int x) //Return type should be bool.
{
    return x<=p;
}

Inside quicksort

std::vector<int>::iterator mid = partition(first,last,pred);
quickSort(first,mid-1);
quickSort(mid,last);

Rest, check how you are calling it.

answered Jan 8, 2014 at 9:16

doptimusprime

9,4416 gold badges58 silver badges94 bronze badges

1 Comment

Bartek Banachewicz Over a year ago

Named predicate looks so passe.

Collectives™ on Stack Overflow

How do I use C++ library algorithms partition function to quicksort?

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related