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