algorithm - クイックソートの中央値の中央値を見つける

Question

中央値アルゴリズムの中央値を使用したクイックソートに取り組んでいます。通常、選択ソートを使用して、5 つの要素のサブ配列の中央値を取得します。ただし、サブアレイが数千ある場合は、千の中央値の中央値を見つける必要があることを意味します。最適ではないため、選択ソートを使用してその中央値を見つけることはできないと思います。

質問：

誰かがその中央値を見つけるためのより良い方法を提案できますか? 前もって感謝します。

Answer 1

The median-of-medians algorithm doesn't work by finding the median of each block of size 5 and then running a sorting algorithm on them to find the median. Instead, you typically would sort each block, take the median of each, then recursively invoke the median-of-medians algorithm on these medians to get a good pivot. It's very uncommon to see the median-of-medians algorithm used in quicksort, since the constant factor in the O(n) runtime of the median-of-medians algorithm is so large that it tends to noticeably degrade performance.

There are several possible improvements you can try over this original approach. The simplest way to get a good pivot is just to pick a random element - this leads to Θ(n log n) runtime with very high probability. If you're not comfortable using randomness, you can try using the introselect algorithm, which is a modification of the median-of-medians algorithm that tries to lower the constant factor by guessing an element that might be a good pivot and cutting off the recursion early if one is found. You could also try writing introsort, which uses quicksort and switches to a different algorithm (usually heapsort) if it appears that the algorithm is degenerating.

Hope this helps!