Quicksort function with vector object C++

Question

I'm trying to convert this function to use a vector object instead of an integer array. The vector object looks like this:

std::vector<Heltal *> htal;

The Heltal class contains a private integer named heltal.

How would I sort the htal vector using the function below?

void Array::Sort(int a[], int first, int last)
{
    int low = first;
    int high = last;
    int x = a[(first+last)/2];
    do {
        while(a[low] < x) {
            low++;
        }
        while(a[high] > x) {
            high--;
        }
        if(low<=high) {
            std::swap(a[low],a[high]);
            low++;
            high--;
        }
    } while(low <= high);
    if(first < high)
        Array::Sort(a,first,high);
    if(low < last)
        Array::Sort(a,low,last);
}

have you tried? there should be no change. Also you dont need the Array:: in Array::Sort(a,low,last); — Karthik T
– Karthik T, Commented Dec 6, 2012 at 1:15
Yes I've tried with replacing the int a[] parameter with the htal parameter but I doubt storing lots of Heltal objects in the function is the best way to do it. — Kraffs
– Kraffs, Commented Dec 6, 2012 at 1:16
Kerrek SB feel free to recommend a better method if you know one. — Kraffs
– Kraffs, Commented Dec 6, 2012 at 1:17

wjl · Accepted Answer · 2012-12-09 21:41:56Z

5

The correct solution is to ditch your custom sort and use std::sort from <algorithm>. This will pretty much be guaranteed to be faster and more optimal in almost every case. Then you just have:

#include <algorithm>
...
std::vector<Heltal *> htal;
...
// sort by pointer value
std::sort(htal.begin(), htal.end());

If you want to sort by object value rather than pointer value, either use std::vector<Heltal> instead of std::vector<Heltal *> (which is almost certainly what you should be doing anyway), or pass a comparison function to std::sort.

Example using C++11 lambda for this:

std::sort(htal.begin(), htal.end(), [](Heltal *a, Heltal *b) { return *a < *b; });

edited Dec 9, 2012 at 21:41

user283145

answered Dec 6, 2012 at 1:23

wjl

7,8752 gold badges38 silver badges44 bronze badges

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

6 Comments

Mark Over a year ago

I believe he wants to sort by an int value inside of the object.

Kraffs Over a year ago

That is correct Mark, the vector object can be printed like this (the only way I know of at least) htal[0][0].

wjl Over a year ago

@Kraffs if you have operator< defined for your class, then you can use std::sort just fine, you don't need to get at any internal members. Alternately, you can make the comparison function you pass to std::sort a friend of the class.

Mark Over a year ago

Ha, ha, sorry wjl with that little tidbit of information, looks like your solution correct. Now I just feel like we are doing @Kraffs homework though.

wjl Over a year ago

@Mark perhaps you're right! But if it's quicksort homework the professor probably wont like just using std::sort ... =)

|

Collectives™ on Stack Overflow

Quicksort function with vector object C++

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related