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

28

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

  1. В худшем случае сложность времени : O(n2)

  2. Количество сравнений : O(n2)

  3. Наилучшая временная сложность :

    • Вид пузыря: O(n)
    • Сортировка выбора: O(n2)
  4. Средняя сложность по времени кейса :

    • Вид пузыря: O(n2)
    • Сортировка выбора: O(n2)
RYO
источник

Ответы:

32

Все сложности, которые вы указали, верны, однако они даны в обозначениях Big O , поэтому все аддитивные значения и константы опущены

Чтобы ответить на ваш вопрос, нам нужно сосредоточиться на подробном анализе этих двух алгоритмов. Этот анализ можно сделать вручную или найти во многих книгах. Я буду использовать результаты Кнута Искусство компьютерного программирования .

Среднее количество сравнений:

  • Вид пузыря : 12(N2NlnN(γ+ln21)N)+O(N)
  • Вид вставки : 14(N2N)+NHN
  • Сортировка выбора : (N+1)HN2N

Теперь, если вы построите эти функции, вы получите что-то вроде этого: сюжет Plot2

Как видите, пузырьковая сортировка значительно ухудшается с увеличением количества элементов, даже если оба метода сортировки имеют одинаковую асимптотическую сложность.

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

Я пропустил анализ сложности времени, потому что он зависит от реализации, но можно использовать аналогичные методы.

Бартош Прзыбыльски
источник
У меня проблема с «мы можем случайным образом переставить входную последовательность для получения среднего случая». Почему это можно сделать быстрее, чем время, необходимое для сортировки?
Сашо Николов
1
NNO(NlogN)N
Я предполагаю, что был сонным, вы правы, последовательность может быть переставлена ​​в линейное время.
Сашо Николов
HN=Θ(logN)
Гамма = 0,577216 - постоянная Эйлера-Маскерони. Соответствующая глава - «Искусство программирования», том 3, раздел 5.2.2, стр. 109 и 129. Как вы построили случай сортировки пузырьков, особенно термин O (sqrt (N))? Вы просто пренебрегали этим?
mxmlnkn
11

O

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

n/41

k×nkn/2(n1)×(n2)/2

Таким образом, асимптотический предел дает хорошее представление о том, как растут затраты на алгоритм по сравнению с размером входных данных, но ничего не говорит об относительной производительности различных алгоритмов в одном наборе.

Pedro
источник
1
это даже очень хороший ответ
Grijesh Chauhan
какую книгу вы предпочитаете?
Грижеш Чаухан
@GrijeshChauhan: Книги - дело вкуса, поэтому примите любую рекомендацию с долей соли. Мне лично нравятся «Введение в алгоритмы» Кормена, Лизерсона и Ривеста, в котором дается хороший обзор по ряду тем, и серия «Искусство компьютерного программирования» Кнута, если вам нужно больше / все подробности по какой-либо конкретной теме. Вы можете проверить, задавался ли здесь вопрос о книгах ранее, или опубликовать этот вопрос, если он не задан.
Педро
Для меня третий пункт в вашем ответе является фактическим ответом. Не приведены графики для больших входов, приведенные в другом ответе.
сверхобмена
3

Bubble sort использует больше времени подкачки, тогда как сортировка выбора избегает этого.

При использовании выбора сортировки это меняет nвремя не более. но при использовании пузырьковой сортировки, он почти переставляется n*(n-1). И, очевидно, время чтения меньше, чем время записи даже в памяти. Время сравнения и другое время выполнения можно игнорировать. Так что время обмена является критическим узким местом проблемы.

simonmysun
источник
Я думаю, что другой ответ Бартека более разумен, но я не могу голосовать или комментировать ... Кстати, я все еще думаю, что время написания влияет больше и надеюсь, что он может принять это во внимание, если он это увидит и согласится.
simonmysun
Вы не можете просто игнорировать количество сравнений, поскольку существуют случаи, когда время, потраченное на сравнение двух элементов, может значительно превышать время, затрачиваемое на обмен двух элементов. Рассмотрим связанный список чрезвычайно длинных строк (скажем, по 100 тыс. Символов каждая). Чтение каждой строки займет гораздо больше времени, чем переназначение указателя.
Ирвин Лим
@ IrvinLim Думаю, вы правы, но мне, возможно, придется посмотреть статистические данные, прежде чем я передумаю.
simonmysun