4
\$\begingroup\$

I was wondering if this implementation of quicksort could be improved. Are there any things that I have done wrong?

template<typename Element>
size_t partition_quickSort(Element arr[], size_t start, size_t end) {
    auto pivot = arr[end];
    size_t index_partition = start;

    for (size_t i = start; i < end; ++i) {
        if (arr[i] <= pivot) {
            std::swap(arr[index_partition++], arr[i]);
        }
    }

    std::swap(arr[index_partition], arr[end]);
    return index_partition;
}

template<typename Element>
void quick_sort(Element arr[], size_t start, size_t end) {
    if (start < end) {
        size_t partition = partition_quickSort(arr, start, end);
        quick_sort(arr, start, partition - 1);
        quick_sort(arr, partition + 1, end);
    }
}
template<typename Element>
void quick_sort(Element arr[], size_t size) {
    quick_sort(arr, 0, size - 1);
}
\$\endgroup\$
4
\$\begingroup\$
  1. There is just one thing wrong with your code.
    Don't ever call std::swap using a qualified name. Doing so cuts out user-defined functions which might be better, or actually viable. Use using std::swap; swap(*pa, *pb); or maybe std::iter_swap(pa, pb);.

  2. Next, there's on thing sub-optimal. You are passing the range, as well as start and end. Knowing where in the overall range the part you are currently processing is does not help, so you can eliminate an argument.

  3. Work on genericity by following C++ conventions.
    Useing half-open iterator-ranges allows wider application, you only need mutable forward-iterators.

  4. Finally, Don't use <= for comparing the elements. All the standard algorithms only use <, and there's no compelling reason to break with that convention.

template <class ForwardIter>
void quicksort(const ForwardIter begin, const ForwardIter end) {
    if (begin == end) return;
    auto cur = begin;
    if (++cur == end) return;
    auto mid = begin;
    for (; cur != end; ++cur)
        if (*cur < *begin)
            std::iter_swap(cur, ++mid);
    std::iter_swap(begin, mid);
    quicksort(begin, mid);
    quicksort(++mid, end);
}
\$\endgroup\$
1
\$\begingroup\$

To add to @Deduplicator suggestions, I would recommend you improve your runtime. I mean there is nothing wrong in the implementation itself but currently you are using the last element of the array as pivot - this element can be the maximum or the minimum on each iteration making the complexity of this implementation in the worst case \$O(n^2)\$.

However if you take the median as pivot in quicksort you are bound to do the job with the least operations as possible (at least asymptotically \$O(n\log n)\$). Be aware that in order to get to this you need an algorithm that finds a median in complexity of \$O(n)\$.

There are quite a lot of information sources on the subject.

You should take a look here.

\$\endgroup\$
  • 3
    \$\begingroup\$ Well, there are other strategies that also prevent worst case \$O(n^2)\$ runtime, e.g. median-of-three (median of first, mid and last, guaranteed not to be the worst match), or even random (increasingly unlikely to get the worst pivot element multiple times in a row). Both of these (and likely some others) can be calculated in \$O(1)\$. \$\endgroup\$ – hoffmale Nov 14 '17 at 0:01
  • \$\begingroup\$ @hoffmale Median-of-three does not prevent square complexity; consider an array of all items equal... Of course you can handle multiple equal items, e.g. with a Dutch flag algorithm if you expect the case in advance. You can also limit the recursion depth by mixing recursion and iteration, but you can't decrease the total amount of work. In general it's hard to make Quicksort faster than \$O(n^2)\$ in pessimistic case. \$\endgroup\$ – CiaPan Nov 20 '17 at 7:45
  • \$\begingroup\$ @CiaPan: wrt. median-of-three "worst-case": Actually, it does prevent it, if you choose the middle one as pivot and don't move elements equal to the pivot around (after all, it doesn't matter whether they are in the lower or upper part). In that case, this is a perfect best case quicksort example (depth = \$\log_2(n)\$, runtime = \$\mathcal{O}(n \log n)\$. Roughly speaking, Quicksort runtime basically boils down to O(partition) * O(comparisons). O(comparisons) is always the same amount of work (= O(n)), so the partition decides the overall runtime (good = O(log n), bad = O(n)). \$\endgroup\$ – hoffmale Nov 20 '17 at 8:09
  • \$\begingroup\$ @hoffmale The bolded assumption did NOT exist in any previous solution proposal nor any comment. You added it after my comment, and the comment refers to what you said before. Of course you're free to change assumptions during discussion, but I feel free to not play such chase. \$\endgroup\$ – CiaPan Nov 20 '17 at 8:17
  • \$\begingroup\$ @CiaPan: Look at @Deduplicator's answer, point 4. Also, it's not really an extra assumption, but integral part of the general quicksort algorithm (using <or > for comparison instead of <= or >=, though granted, many overlook that point). \$\endgroup\$ – hoffmale Nov 20 '17 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.