Sign in to follow this  

Proper way to use Quicksort?

This topic is 3863 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I just want to know if I should be 'quicksorting' as I add items, or just add them all and apply quicksort afterwards. Also I want to remove duplicates - again, should I look for them as I add them or just add everything and then do a pass to remove duplicates? What's the easiest way? [Edited by - Domarius on May 20, 2007 11:44:28 PM]

Share this post


Link to post
Share on other sites
To answer your question, it would definitely be much faster to apply quicksort afterwards. Applying quicksort every time an element is added just gives you so many unneeded comparisons.

To give you some good advice though, have you considered using the C++ std::set container? A set is a sorted associative container (this basically means that elements are automatically sorted upon insertion into the set), it is associative in such a way that the key is the element and naturally the element is the key. No two elements can share the same key in a set, thus meaning that all elements within a set are unique.

Share this post


Link to post
Share on other sites
Yeh that's what I should be doing hey... I need to dig up my Uni programming class notes... I have to inherit the set class and implement a < operator... or something.

Share this post


Link to post
Share on other sites
Quote:
Yeh that's what I should be doing hey... I need to dig up my Uni programming class notes... I have to inherit the set class and implement a < operator... or something.


Ummmm..... No you dont inherit from set, all you need to do is give the class you want to make a set of an operator< or provide a comparer to the set constructor...


struct foo
{
foo(int i, int j) : i(i), j(j) { }
int i;
int j;
}

bool operator<(foo lhs, foo rhs)
{
return lhs.i < rhs.i;
}

bool j_comparer(foo lhs, foo rhs)
{
return lhs.j < rhs.j;
}

int main()
{
std::set<foo> set_i; // uses operator< to compare foo's
std::set<foo, bool (foo, foo)> set_j(j_comparer); // uses j_comparer to compare foo's
}

Share this post


Link to post
Share on other sites
If there's a lot of insertions/deletions while your program runs, use a std::set/map. If there's just a bunch of insertions at the start, and the rest are all reads, use a vector, sort it once, and binary_search on it.

Share this post


Link to post
Share on other sites

This topic is 3863 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this