Как использовать медиану массива в качестве опоры для быстрой сортировки

Question

я должен написать алгоритм быстрой сортировки, который использует медиану массива в качестве опоры. Исходя из моего общего понимания того, что я прочитал в книге, я должен использовать алгоритм выбора, в котором я разделяю массив на n / 5 подмассивов, сортирую каждый из подмассивов с помощью сортировки вставкой, находим медиану, затем рекурсивно вызываю выберите алгоритм, чтобы найти медиану медиан. Я даже не уверен, как начать это, и я довольно смущен. вызов алгоритма selectMedian должен выглядеть примерно так: SelectMedian (int first, int last, int i) где i - это i-й индекс, который я хочу выбрать (в данном случае это будет средний индекс, поэтому array.length / 2 ). Книга, которую я читаю, дает такое описание:

The algorithm in words (if n>1):

1. Divide n elements into groups of 5
2. Find median of each group (use insertion sort for this)
3. Use Select() recursively to find median x of the  n/5
medians
4. Partition the n elements around x.  Let k = rank(x)
5. if (i == k) then return x
if (i < k) then use Select() recursively to find i-th
smallest element in first partition else (i > k) use 
Select() recursively to find (i-k)th smallest element in 
last partition.

Может кто-нибудь помочь мне в написании этого алгоритма? спасибо!

Answer 1

Это действительно необходимо? Почему бы не использовать медиану из трех , где вы выбираете пивот на основе медианы из трех значений, т.е. первое, среднее и последнее значения.

Или вы можете даже использовать random pivot, который резко снизит шансы на то, что в QuickSort будет наихудшее время O (N²), что также может быть подходящим для ваша реализация.

Answer 2

QUICKSORT2(A, p, r)
if p<r
    median=floor((p + r) /2) - p + 1
    q=SELECT(A, p, r, median)
    q=PARTITION2(A, p, r, q)
    QUICKSORT2(A, p, q-1)
    QUICKSORT2(A, q+1, r)

PARTITION2(A, p, r, q)
switch between A[r] and A[q]
return PARTITION(A, p, r)

Answer 3

Полагаю, вы можете определить n / 5 подмассивов по 5 элементов в каждом.

Найти медиану подмассива довольно просто: вы смотрите на каждый элемент и находите элемент, который имеет два меньших элемента.

Например, у вас есть 1 4 2 3 5. 1 не имеет меньших элементов. 4 имеет три меньших элемента. 2 имеет один меньший элемент. 3 имеет два меньших элемента; это тот, который вы хотите.

Теперь вы нашли n / 5 медиан. Вы хотите найти медиану медиан, поэтому снова запускаете алгоритм.

Пример:

1 7 2 4 9 0 3 8 5 6 1 4 7 2 3

[1 7 2 4 9] [0 3 8 5 6] [1 4 7 2 3]

findMedian ([1 7 2 4 9]) = 4;

findMedian ([0 3 8 5 6]) = 5;

findMedian ([1 4 7 2 3]) = 3;

[4 5 3]

findMedian ([4 5 3]) = 4;

4 - ваш стержень.

Причина, по которой вы делаете это, состоит в том, чтобы попытаться разделить массив равномерно; если ваш массив разбит на две части, вы получите производительность O (N ^ 2); если ваш массив разделен равномерно, вы получите производительность O (NlogN).

Выбор случайного поворота означает, что вы могли бы получить любой из них - на практике это сбалансировалось бы в O (NlogN), но многим приложениям нужна стабильная производительность, а случайная быстрая сортировка не согласована от запуска к запуску .

Причина, по которой мы используем 5 (вместо 3 или 7), заключается в том, что мы добавляем еще один критерий сложности времени при поиске медианы - этот термин должен быть меньше O (NlogN), но вы хотите, чтобы он был таким же маленьким насколько это возможно. При использовании 3 вы получаете O (N ^ 2), при использовании 5 вы получаете O (NlogN), а 5 - наименьшее число, для которого это верно.

(алгоритм нахождения медианы в линейном времени был дан Блюмом, Флойдом, Праттом, Ривестом и Тарьяном в их статье 1973 года «Границы времени для выбора» и ответил на известную открытую задачу)