Сравнение эффективности пузырьковой сортировки, сортировки выбором и сортировкой вставками

У меня есть следующее понимание: и пузырьковая сортировка, и сортировка вставками имеют временные сложности.

  • Лучшее: Ω(n)
  • Среднее значение: Θ(n^2)
  • Худший: O(n^2)

В то время как сортировка выбора имеет все временные сложности (лучший, средний и худший): (n ^ 2)

После этого вот мои вопросы, основанные на том, что я обычно слышу об этих алгоритмах:

  1. Пузырьковая сортировка считается наименее эффективным алгоритмом / считается наравне с сортировкой выбором. Почему так? (так как я знаю, согласно Ω, пузырьковая сортировка намного лучше, чем выбор.)
  2. Сортировка вставками считается улучшением по сравнению с пузырьковой сортировкой и сортировкой выбором. Почему именно так? (опять же, к сложностям времени, хотя я понимаю, что это лучше, чем сортировка выбором, но это также ТОЧНО то же самое, что и пузырьковая сортировка).

sorting algorithm selection-sort bubble-sort insertion-sort
person Rajdeep Biswas    schedule 08.12.2018    source источник
comment
1. В лучшем случае сложность — довольно бессмысленный показатель. Вас интересуют средний и худший случаи. 2. Большая сложность — это еще не все, значение имеют постоянные факторы.   -  person n. 1.8e9-where's-my-share m.    schedule 08.12.2018
comment
Я дал информацию о сравнениях во вставке/пузырьке в вашей прошлой теме   -  person MBo    schedule 08.12.2018
comment
Шпаргалка Big-O — мой справочник по этому   -  person MTCoster    schedule 09.12.2018
comment
Я не профессионал в этом вопросе, но я думаю, что пузырьковая сортировка считается наименее эффективной, потому что она имеет большее количество свопов по сравнению с сортировкой выбором.   -  person seulgibear    schedule 09.12.2018
comment
Здравствуйте еще раз, я изучил этот вопрос и нашел это. Возможно, ты захочешь это прочитать. Удачи~   -  person seulgibear    schedule 09.12.2018

Ответы (1)


arrow_upward
-1
arrow_downward

Насколько я знаю, пузырьковая сортировка является худшей с точки зрения эффективности, особенно если у вас есть отсортированные в обратном порядке списки или большие списки. Лучший случай для пузырьковой сортировки — это когда почти весь список уже отсортирован. Вы должны проверить сложность каждого алгоритма в вашем случае, чтобы выяснить, какой из них лучше.

person Codrut    schedule 08.12.2018