Быстрая сортировка с «медианой трех» сводный выбор: понимание процесса

/* @param left
*       the left boundary for the subarray from which to find a pivot
* @param right
*       the right boundary for the subarray from which to find a pivot
* @return
*       the index of the pivot (middle index); -1 if provided with invalid input
*/
int QS::medianOfThree(int left, int right){}

/* @param left
*       the left boundary for the subarray to partition
* @param right
*       the right boundary for the subarray to partition
* @param pivotIndex
*       the index of the pivot in the subarray
* @return
*       the pivot's ending index after the partition completes; -1 if
*       provided with bad input
*/
int QS::partition(int left, int right, int pivotIndex){}

/*
* sortAll()
*
* Sorts elements of the array.  After this function is called, every
* element in the array is less than or equal its successor.
*
* Does nothing if the array is empty.
*/
void QS::sortAll(){}

/*
* medianOfThree()
*
* The median of three pivot selection has two parts:
*
* 1) Calculates the middle index by averaging the given left and right indices:
*
* middle = (left + right)/2
*
* 2) Then bubble-sorts the values at the left, middle, and right indices.
*
* After this method is called, data[left] <= data[middle] <= data[right].
* The middle index will be returned.
*
* Returns -1 if the array is empty, if either of the given integers
* is out of bounds, or if the left index is not less than the right
* index.
*
* @param left
*       the left boundary for the subarray from which to find a pivot
* @param right
*       the right boundary for the subarray from which to find a pivot
* @return
*       the index of the pivot (middle index); -1 if provided with invalid input
*/
int QS::medianOfThree(int left, int right){}

/*
* Partitions a subarray around a pivot value selected according to
* median-of-three pivot selection.
*
* The values which are smaller than the pivot should be placed to the left
* of the pivot; the values which are larger than the pivot should be placed
* to the right of the pivot.
*
* Returns -1 if the array is null, if either of the given integers is out of
* bounds, or if the first integer is not less than the second integer, OR IF THE
* PIVOT IS NOT BETWEEN THE TWO BOUNDARIES.
*
* @param left
*       the left boundary for the subarray to partition
* @param right
*       the right boundary for the subarray to partition
* @param pivotIndex
*       the index of the pivot in the subarray
* @return
*       the pivot's ending index after the partition completes; -1 if
*       provided with bad input
*/
int QS::partition(int left, int right, int pivotIndex){}

Начните с понимания быстрой сортировки сначала, медиана из трех затем.

Для выполнения быстрой сортировки вы:

1. Выберите элемент из массива, который вы сортируете (подойдет любой элемент, но к которому лучше всего обратиться, к которому мы вернемся).
2. Переупорядочьте массив так, чтобы все элементы, меньшие, чем тот, который вы выбрали, были перед ним в массиве, и все те, которые были больше, чем после него.
3. Рекурсивно делайте вышеописанное с сетами до и после выбранного вами предмета.

Шаг 2 называется «операция с разделами». Подумайте, было ли у вас следующее:

3 2 8 4 1 9 5 7 6

Теперь предположим, что вы выбрали первое из этих чисел в качестве основного элемента (тот, который мы выбрали на шаге 1). После применения шага 2 мы получим что-то вроде:

2 1 3 4 8 9 5 7 6

Значение 3 теперь находится в правильном месте, и каждый элемент находится на правильной стороне этого. Если мы теперь отсортируем левую часть, мы получим:

1 2 3 4 8 9 5 7 6.

Теперь давайте рассмотрим только элементы справа от него:

4 8 9 5 7 6.

Если мы выберем 4 чтобы повернуть дальше, мы в итоге ничего не меняем, поскольку это было в правильном положении для начала Для набора элементов слева от него пусто, поэтому тут делать нечего. Теперь нам нужно отсортировать набор:

8 9 5 7 6.

Если мы используем 8 в качестве нашей оси, мы можем получить:

5 7 6 8 9.

9 Теперь справа от него находится только один элемент, поэтому, очевидно, уже отсортированы. 5 7 6 осталось сортировать. Если мы поворачиваемся на 5 в итоге мы оставляем это в покое, и нам просто нужно разобраться 7 6 в 6 7,

Теперь, учитывая все эти изменения в более широком контексте, мы получили следующее:

1 2 3 4 5 6 7 8 9.

Итак, чтобы снова подвести итог, быстрая сортировка выбирает один элемент, перемещает элементы вокруг него так, чтобы они все были правильно расположены относительно этого одного элемента, а затем рекурсивно делает то же самое с оставшимися двумя наборами, пока не останется не отсортированных блоков, и все будет отсортирован.

Давайте вернемся к вопросу, который я выдумал, когда сказал, что «любой предмет подойдет». Хотя это верно для любого элемента, выбранный вами элемент повлияет на производительность. Если вам повезет, вы в конечном итоге сделаете это за несколько операций, пропорциональных n log n, где n — количество элементов. Если вам просто повезет, это будет немного большее число, все еще пропорциональное n log n. Если вам действительно не повезло, это будет число, пропорциональное числу, пропорциональному n².

Так что же лучше всего выбрать? Лучшее число — это элемент, который окажется в середине после того, как вы выполните операцию разбиения. Но мы не знаем, что это за предмет, потому что, чтобы найти средний предмет, нам нужно отсортировать все предметы, и именно это мы и пытались сделать в первую очередь.

Итак, есть несколько стратегий, которые мы можем использовать:

1. Просто зайди к первому, потому что, ну почему бы и нет?

2. Выберите среднюю, потому что, возможно, массив уже по какой-то причине уже отсортирован или почти отсортирован, а если нет, то выбор не хуже, чем у любого другого.

3. Выберите случайный.

4. Выберите первый, средний и последний, и выберите медиану из этих трех, потому что, по крайней мере, это будет лучший из этих трех вариантов.

5. Выберите медиану из трех для первой трети массива, медиану из трех второй трети, медиану из трех из последней трети и затем, наконец, выберите медиану из этих трех медиан.

У них есть свои плюсы и минусы, но, в целом, каждый из этих вариантов дает лучшие результаты при выборе лучшего центра, чем предыдущий, но за счет затрат большего времени и усилий на выбор этого центра. (У Random есть дополнительное преимущество в том, что он побеждает в случаях, когда кто-то намеренно пытается создать данные, с которыми вы будете вести себя в худшем случае, как часть некоторой DoS-атаки).

Мое назначение гласит, что для продолжения разбиения массива стержень должен находиться между левой и правой границами.

Да. Рассмотрим выше снова, когда мы отсортировали 3 в правильное положение и отсортировали влево:

1 2 3 4 8 9 5 7 6.

Теперь, здесь нам нужно отсортировать диапазон 4 8 9 5 7 6, граница это линия между 3 и 4 и линия между 6 и конец массива (или другой способ взглянуть на него, граница 4 и 6, но это включительно границы, включая эти предметы). Для трех мы выбираем, следовательно, 4 (первый) 6 (последний) и либо 9 или 5 в зависимости от того, округляем ли мы вверх или вниз при делении счетчика на 2 (мы, вероятно, округляем вниз, как обычно при целочисленном делении, поэтому 9). Все они находятся внутри границы раздела, который мы сейчас сортируем. Следовательно, наша средняя из трех 6 (или если бы мы собрали, мы бы пошли на 5).

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

* 2) Then bubble-sorts the values at the left, middle, and right indices.
*
* After this method is called, data[left] <= data[middle] <= data[right].
* The middle index will be returned.

[5,3,1,7,9]

[9,3,1,7,5]

[1,3,7,9,5]

[1,3,5,9,7]