Why do we use quicksort instead of heapsort?

How do I use the stl partition function in C++?

• //I want to use it for a quick sort but it won't work, what exactly must //partition accept and return? void quicksort( int x[], int n ) { if(n <= 1) return; int m=partition(x, n); quicksort()(x, m); quicksort()(x + m + 1, n - m - 1); }

• Answer:

  It accepts two iterators and a predicate, and it returns an iterator pointing to the first element of the second partition. In your case, the iterators would be int pointers. The predicate needs to be a function or function object which will take one argument, an int in your case, since you're sorting an array of ints. And it should return true for elements which you want to put in the first partition, and false for elements you want to put in the second partition. Here's a function object class that you could use:     struct LessThanN     {         int N;         LessThanN(int n) :N(n) { }         bool operator() (int x) const         {             return x < N;         }     }; If you're not familiar with function objects. They are objects that act like functions, by having operator() overloaded. Because they're objects, they can have state, unlike normal functions. Anyway, you can use LessThanN like this. First create an object:     LessThanN less_than_10(10); Now less_than_10 acts like a function that takes an int argument, and returns true if it is less than 10, and false if it is greater than or equal to 10.     less_than_10(5); // returns true     less_than_10(15); // returns false You can use this class to construct a predicate to pass as the third argument to partition. You just need to decide on a value for the pivot each time. For simplicity, I'll write this just using the first element in the range, but this is going to have bad performance on certain arrangements, though it should still be fast on average. If you want to improve it, look into pivot selection methods, such as median-of-3, which looks at the first element, the last element and the center element, and selects their median as the pivot.     void quicksort( int * x, int n )     {         if (n<=1) return;         LessThanN pred(x[0]);         int * pivot = partition(x, x + n, pred);         int left_len = pivot - x;         int right_len = n - left_len - 1;         quicksort(x, left_len);         quicksort(pivot + 1, right_len);     }