Алгоритм быстрой сортировки

Question

Я использовал алгоритм быстрой сортировки для сортировки

11 8 9 4 2 5 3 12 6 10 7

и я получил список:

4 3 2 5 9 11 8 12 6 10 7.

5 использовался в качестве точки разворота. Теперь я застрял. Как перейти к сортировке нижнего и верхнего списков?

pivot = 5 11 8 9 4 2 5 3 12 6 10 7

• Переместить шарнир в положение 0 5 8 9 4 2 11 3 12 6 10 7
• i (позиция 1 = 8)
• j (позиция 6 = 3) ⇒ поменять местами 8 и 3 5 3 9 4 2 11 8 12 6 10 7
• i (позиция 2 = 9)
• j (позиция 4 = 2) ⇒ поменять местами 9 и 2 5 3 2 4 9 11 8 12 6 10 7
• i (позиция 3 = 4) - элементы не меньше 5 ⇒ поменяйте местами 5 и 4 4 3 2 5 9 11 8 12 6 10 7 - список после раздела

Answer 1

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

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

Как только вы достигаете точки, где набор содержит только один элемент, вы останавливаетесь.

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

Answer 2

Ключевым компонентом алгоритма является то, что выбранное значение сводки пришло из исходного списка, что означает (в вашем случае) элемент со значением 5 теперь в правильной конечной позиции после первого разбиения:

4 3 2 5 9 11 8 12 6 10 7

Это должно быть довольно очевидно и следует простой интуиции. Если каждый элемент слева от элемента меньше, чем этот элемент, а каждый элемент справа больше, то элемент должен быть в правильной, отсортированной позиции.

Понимание, необходимое для понимания всего алгоритма быстрой сортировки, заключается в том, что вы можете просто продолжать делать это для каждого из подсписков - списка значений слева от сводки и списка, содержащего все значения справа - чтобы получить в окончательном отсортированном списке. Это потому что:

• Каждое разбиение помещает еще один элемент в правильное положение
• Каждая итерация удаляет один элемент - сводку - из списка элементов, оставленных для обработки (поэтому в конечном итоге мы достигнем базового случая с нулевым (или одним, в зависимости от того, как вы это делаете) элементами)

Предположим, вы выбрали значение раздела 5 на основе следующего псевдокода:

Math.floor(list.length / 2)

Для наших целей фактический выбор точки разворота не имеет большого значения. Этот работает на ваш оригинальный выбор, поэтому мы пойдем с ним. Теперь давайте доиграем это до конца (начиная с того места, где вы остановились):

concat(qs([4 3 2]), 5,  qs([9 11 8 12 6 10 7])) = 
concat(qs([2]), 3, qs([4]), 5, qs([9, 11, 8, 6, 10, 7]), 12, qs([])) =
concat(2, 3, 4, 5, qs([6, 7]), 8, qs([9, 11, 10]), 12) =
concat(2, 3, 4, 5, qs([6]), 7, qs([]), 8, qs([9, 10]), 11, qs([]), 12) =
concat(2, 3, 4, 5, 6, 7, 8, qs([9]), 10, qs([]), 11, 12) = 
concat(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)

Обратите внимание, что каждый раз, когда вы видите один вызов qs, он будет следовать следующей схеме:

qs(<some_left_list>), <the_pivot>, qs(<some_right_list>)

И каждый вызов qs в одной строке приводит к еще двум таким вызовам в следующей строке (представляя обработку обоих новых подсписков (за исключением того, что я немедленно разбиваю вызовы на qs в списках с одним значением)) .

Хорошая идея - пройти это упражнение самостоятельно. Да, с ручкой и бумагой.