Обе технологии сортировки, быстрая сортировка и сортировка слиянием построены на методе «разделяй и властвуй», при котором набор элементов разделяется, а затем объединяется после перегруппировки. Быстрая сортировка обычно требует больше сравнений, чем сортировка слиянием для сортировки большого набора элементов.
Сравнительная таблица
| Основа для сравнения | Быстрая сортировка | Сортировка слиянием |
|---|---|---|
| Разбиение элементов в массиве | Разделение списка элементов не обязательно делится на половину. | Массив всегда делится на половину (n / 2). |
| В худшем случае сложность | O (n 2) | O (n log n) |
| Хорошо работает на | Меньший массив | Работает нормально в любом типе массива. |
| скорость | Быстрее, чем другие алгоритмы сортировки для небольшого набора данных. | Постоянная скорость во всех типах наборов данных. |
| Требуется дополнительное место для хранения | Меньше | Больше |
| КПД | Неэффективно для больших массивов. | Более эффективным. |
| Метод сортировки | внутренний | внешний |
Определение быстрой сортировки
Быстрая сортировка - широко распространенный алгоритм сортировки, так как он быстр для коротких массивов. Набор элементов многократно разделяется на части, пока его невозможно разделить дальше. Быстрая сортировка также называется сортировкой по разделам . Он использует ключевой элемент (известный как сводный) для разделения элементов. Один раздел содержит те элементы, которые меньше, чем ключевой элемент. Другой раздел содержит те элементы, которые больше, чем ключевой элемент. Элементы отсортированы рекурсивно.
Предположим, что A - это массив A [1], A [2], A [3], …… .., A [n] из n чисел, которые должны быть отсортированы. Алгоритм быстрой сортировки состоит из следующих шагов.
- Первый элемент или любой случайный элемент, выбранный в качестве ключа, предположим, что key = A (1).
- Указатель «low» размещается во втором, а указатель «up» - в последнем элементе массива, т.е. low = 2 и up = n;
- Последовательно увеличивайте указатель «low» на одну позицию до (клавиша A [low]>).
- Постоянно уменьшайте указатель «вверх» на одну позицию до (A [вверх] <= клавиша).
- Если up больше, чем low, поменяйте местами A [low] и A [up].
- Повторяйте шаги 3, 4 и 5 до тех пор, пока условие на шаге 5 не будет выполнено (т.е. вверх <= низкий), затем поменяйте местами A [вверх] с ключом.
- Если элементы слева от ключа меньше ключа, а элементы справа от ключа больше ключа, то массив разделяется на два подмассива.
- Вышеуказанная процедура неоднократно применяется к подмассивам, пока весь массив не будет отсортирован.
Преимущества и недостатки
Обладает хорошим средним поведением. Сложность времени выполнения быстрой сортировки хороша тем, что она быстрее, чем алгоритмы, такие как пузырьковая сортировка, вставка и сортировка. Однако он сложен и очень рекурсивен, поэтому он не подходит для больших массивов.
Определение сортировки слиянием
Сортировка слиянием - это внешний алгоритм, который также основан на стратегии «разделяй и властвуй». Элементы разделяются на подмассивы (n / 2) снова и снова до тех пор, пока не останется только один элемент, что значительно сокращает время сортировки. Он использует дополнительное хранилище для хранения вспомогательного массива. Сортировка слиянием использует три массива, два из которых используются для хранения каждой половины, а третий - для хранения окончательного отсортированного списка. Каждый массив затем сортируется рекурсивно. Наконец, подмассивы объединяются, чтобы получить размер элемента n массива. Список всегда делится на половину (n / 2), отличную от быстрой сортировки.
Пусть A будет массивом из n элементов, которые будут отсортированы A [1], A [2], ………, A [n]. Сортировка слиянием выполняется по заданным шагам.
- Разбейте массив A на примерно n / 2 отсортированного подмассива на 2, что означает, что элементы в (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]), (A [n-1], A [n]) подмассивы должны быть в отсортированном порядке.
- Объедините каждую пару пар, чтобы получить список отсортированных подмассивов размера 4; элементы в подмассивах также расположены в отсортированном порядке (A [1], A [2], A [3], A [4]), ……, (A [k-1], A [k], A [k + 1], A [k + 2]), ……., (A [n-3], A [n-2], A [n-1], A [n]).
- Шаг 2 многократно выполняется, пока не будет только один отсортированный массив размера n.
Преимущества и недостатки
Алгоритм сортировки слиянием работает точно так же и точно, независимо от количества элементов, участвующих в сортировке. Он отлично работает даже с большим набором данных. Тем не менее, он потребляет большую часть памяти.
Ключевые различия между быстрой сортировкой и сортировкой слиянием
- При сортировке слиянием массив должен быть разделен на две половины (т. Е. N / 2). В отличие от быстрой сортировки, нет необходимости делить список на равные элементы.
- Наихудшая сложность быстрой сортировки - O (n2), так как в худшем случае требуется намного больше сравнений. Напротив, сортировка слиянием имеет одинаковую сложность в наихудшем и среднем случаях, то есть O (n log n).
- Сортировка слиянием может хорошо работать с любым типом наборов данных, будь то большой или маленький. Напротив, быстрая сортировка не может хорошо работать с большими наборами данных.
- Быстрая сортировка быстрее, чем сортировка слиянием в некоторых случаях, например, для небольших наборов данных.
- Для сортировки слиянием требуется дополнительное пространство памяти для хранения вспомогательных массивов. С другой стороны, быстрая сортировка не требует много места для дополнительного хранения.
- Сортировка слиянием более эффективна, чем быстрая сортировка.
- Быстрая сортировка - это метод внутренней сортировки, при котором данные, которые должны быть отсортированы, корректируются за раз в основной памяти. И наоборот, сортировка слиянием - это внешний метод сортировки, в котором данные, которые должны быть отсортированы, не могут быть размещены в памяти одновременно, а некоторые должны храниться во вспомогательной памяти.
Заключение
Быстрая сортировка - это более быстрые случаи, но в некоторых ситуациях она неэффективна, а также выполняет много сравнений по сравнению с сортировкой слиянием. Хотя сортировка слиянием требует меньшего сравнения, ей требуется дополнительное пространство памяти 0 (n) для хранения дополнительного массива, тогда как для быстрой сортировки требуется пространство O (log n).
