weblogs : arhuaco : randomized-qsort-trick

The qsort algorithm surprised me again.

In the analysis of the randomized qsort it is assumed that the values to be sorted are different but things go really bad when you have a lot of equal values. For instance, if you have a vector with all N elements set to the same value you will get quadratic behavior from this algorithm.

I noticed this because in a test I filled a vector with random numbers in the range [0, 9] and the algorithm was very slow. Since it didn't make sense I noticed that the implementation of the algorithm that you find in the slides is very bad in this case.

Fortunately it's easy to fix. An excerpt from this example (check the remark):

template <class T>
void qsort(vector <T> &v, int first, int last) {
  if (first >= last)
    return;
  int pivot = partition(v, first, last);
  qsort(v, pivot + 1, last);
  while (pivot > first && v[pivot] == v[pivot - 1]) // This cycle is important!
    pivot--;
  qsort(v, first, pivot - 1);
}

In another lecture I noticed that the teacher is very aware of this but somehow this is not in the slides. Perhaps it's too much information for a single session and they were mostly interested in the proof for the randomized algorithm.

Loading... Discussion

• qsort