QuickSort для сортировки деталей Mergesort?

Question

Ques: Mergesort делит список чисел на две половины и называет себя рекурсивно на обоих из них. Вместо этого вы можете выполнять quicksort в левой половине и объединять в правой половине? Если да, покажите, как он будет сортировать следующий список чисел, показывая каждый шаг. Если нет, объясните, почему вы не можете.

Предполагается, что я должен сортировать список чисел, используя mergesort. Где левая половина должна сортироваться с помощью быстрой сортировки?

Я понял. Ans: Да, мы можем

1. Сортируйте правую половину массива, используя mergesort.
2. Сортировка левой половины с помощью быстрой сортировки.
3. Объединить 2 с помощью функции merge_sort.

Answer 1

Да, вы можете это сделать. Основная идея mergesort заключается в следующем:

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

С точки зрения правильности, на самом деле не имеет значения, как сортировать списки, сгенерированные в части (2). Все, что имеет значение, состоит в том, что эти списки сортируются. Типичная реализация mergesort делает шаг (2) путем рекурсивного применения себя к левой и правой половине, но нет основополагающей причины, по которой вы должны это делать. (На самом деле, в некоторых оптимизированных версиях mergesort вы конкретно do not делают это и вместо этого переключаетесь на такой алгоритм, как сортировка вставки, когда массивы становятся достаточно маленькими).

В вашем случае вы правы, что использование quicksort слева и mergesort справа все равно будет производить отсортированную последовательность. Однако способ, которым он будет работать, будет выглядеть совсем иначе, чем то, что вы описываете. Что бы закончилось, это примерно так: первая половина массива будет быстро сортироваться (потому что вы быстро сортируете левую половину), тогда вы рекурсивно сортируете правую половину. В первой половине , что будет быстро сортироваться, вы рекурсивно сортируете правую половину. Первая половина что бы получить quicksorted и т.д. В целом это будет выглядеть примерно так:

• Вы QuickSort первую половину массива, то первая половина того, что осталось, то первая половина того, что это слева и т. д., пока не осталось элементов.
• Затем, работая слева направо, вы бы объединить два последних элемента вместе, то последние четыре, то последние восемь и т.д.

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

Answer 2

Нет, вы не можете этого сделать. По крайней мере, если вы все же хотите назвать это «сортировка слияния». Наиболее фундаментальное различие между сортировкой слияния и быстрой сортировкой состоит в том, что первый является стабильным алгоритмом, то есть одинаково упорядоченные элементы сохраняют относительные позиции без изменений после сортировки. Это важно во многих сценариях. Если вы сортируете вторую половину, используя быструю сортировку, относительное положение равных элементов может (и, скорее всего, будет) изменяться. Полученный набор не сохранит стабильность, поэтому он не может считаться сортировкой слияния.

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