Рубрики

Почему быстрая сортировка предпочтительнее для массивов и сортировка слиянием для связанных списков?

Почему быстрая сортировка предпочтительнее для массивов?

Ниже приведены рекурсивные и итеративные реализации быстрой сортировки и сортировки слиянием для массивов.

Рекурсивная быстрая сортировка по массиву.
Итеративная быстрая сортировка для массивов.
Рекурсивная сортировка слиянием для массивов
Итеративная сортировка слиянием для массивов

  • Быстрая сортировка в общем виде представляет собой сортировку на месте (т. Е. Она не требует дополнительного хранилища), тогда как сортировка слиянием требует O (N) дополнительного хранилища, N обозначает размер массива, который может быть довольно дорогим. Выделение и перераспределение дополнительного пространства, используемого для сортировки слиянием, увеличивает время работы алгоритма.
  • Сравнивая среднюю сложность, мы обнаруживаем, что оба типа сортов имеют O (NlogN) средней сложности, но константы различаются. Для массивов сортировка слиянием теряется из-за использования дополнительного пространства памяти O (N).
  • Большинство практических реализаций быстрой сортировки используют рандомизированную версию. Рандомизированная версия имеет ожидаемую временную сложность O (nLogn). Наихудший случай возможен и в рандомизированной версии, но наихудший случай не возникает для определенного шаблона (например, отсортированного массива), и рандомизированная быстрая сортировка хорошо работает на практике.
  • Быстрая сортировка также является алгоритмом сортировки, дружественным к кешу, поскольку имеет хорошую локальность при использовании для массивов.
  • Быстрая сортировка также является хвостовой рекурсией , поэтому выполняется оптимизация хвостовых вызовов.

Почему сортировка слиянием предпочтительнее для связанных списков?

Ниже приведены реализации Quicksort и Mergesort для односвязных и двусвязных списков.

Быстрая сортировка для двусвязного списка
Быстрая сортировка для односвязного списка
Сортировка слиянием для односвязного списка
Сортировка слиянием для двусвязного списка

  • В случае связанных списков случай отличается в основном из-за различий в распределении памяти массивов и связанных списков. В отличие от массивов, узлы связанного списка могут не быть смежными в памяти.
  • В отличие от массива, в связанный список мы можем вставлять элементы посередине в O (1) дополнительное пространство и O (1) время. Поэтому операция слияния сортировки слиянием может быть реализована без дополнительного места для связанных списков.
  • В массивах мы можем осуществлять произвольный доступ, поскольку элементы непрерывны в памяти. Допустим, у нас есть целочисленный (4-байтовый) массив A, и пусть адрес A [0] будет равен x, чтобы получить доступ к A [i], мы можем напрямую получить доступ к памяти в (x + i * 4). В отличие от массивов, мы не можем делать произвольный доступ в связанном списке.
  • Быстрая сортировка требует большого количества такого доступа. В связанном списке для доступа к i-му индексу мы должны перемещать каждый узел от головы до i-го узла, поскольку у нас нет непрерывного блока памяти. Поэтому накладные расходы увеличиваются для быстрой сортировки. Сортировка слиянием обращается к данным последовательно, и потребность в произвольном доступе низка.

Статьи по Теме:

Спасибо Саяну Мухопадхяю за предоставление первоначального черновика для вышеуказанной статьи. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Почему быстрая сортировка предпочтительнее для массивов и сортировка слиянием для связанных списков?

0.00 (0%) 0 votes