Актуальность Quicksort, Heapsort и Bubblesort

Question

В настоящее время я обучаюсь на 1-м курсе магистратуры в области прикладных вычислений, который предназначен для обучения людей, не имеющих опыта в области вычислительной техники, и подготовки к ускоренным курсам по разработке программного обеспечения и разработке и подготовке нас к карьере в технологической отрасли. , Один из классов курса, Advanced Programming Techniques, охватывает ряд алгоритмов сортировки, реализованных в C ++, а именно Quicksort, Heapsort и Bubblesort. Тем не менее, ряд студентов сказал нам, что эти алгоритмы не имеют отношения к промышленности и не широко используются. Верно ли это, и если да, то на какие алгоритмы сортировки я должен смотреть?

Answer 1

Быстрая сортировка, Heapsort и Buublesort. Тем не менее, ряд студентов сказал нам, что эти алгоритмы не имеют отношения к промышленности и не широко используются.

Это явно ложно. Вы увидите Quicksort в дикой природе и, вероятно, даже heapsort.

Это правда, и если да, то на какие алгоритмы сортировки я должен смотреть?

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

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

Таким образом, мы используем, скажем, вычисление чисел Фибоначчи в качестве примера рекурсивного алгоритма, чтобы изучить концепцию рекурсии, а не так много, чтобы научиться вычислять числа Фибоначчи. Это редко требуется в дикой природе (если только у вас нет проблем с Project Euler). (И реализация Фибоначчи через рекурсию в любом случае ужасна.)

Answer 2

• Bubblesort имеет чрезвычайно плохую производительность и, вероятно, просто имеет образовательную ценность, чтобы продемонстрировать это.

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

• Быстрая сортировка , с другой стороны, действительно быстрая, но имеет ужасный худший случай для некоторых неудачных вводов.

На практике вы не будете реализовывать ни из них, а использовать существующие, высоко оптимизированные процедуры сортировки (возможно, именно это они и имеют в виду).

Это будут комбинации измножество алгоритмов противодействия дефицитам каждого из них.Вы можете увидеть Introsort, который использует quicksort + heapsort для уменьшения наихудшего сценария или даже сортировку вставкой для небольших входных данных.

Answer 3

Я видел несколько реализаций быстрой сортировки, хотя Bubblesort используется редко, за исключением случаев обучения. Обучение кого-то, почему что-то ужасное, может быть полезным, что может быть частью того, чего вам здесь не хватает, почему вы должны немного об этом знать. Хотя некоторые люди могут просто сказать "Дух!" почему Bubblesort ужасен, могут быть некоторые, которые должны найти лучшее доказательство того, почему другие способы лучше. Сортировка - это проблема, которая была хорошо изучена, в то время как другие общие проблемы могут быть недостаточно изучены, например. посмотрите на различные алгоритмы для решения NP-полных задач, таких как задача коммивояжера.

Answer 4

Пузырьковая сортировка медленная, O (n ^ 2). Наиболее часто используется быстрая сортировка. Среднее время - O (n log n), но O (n ^ 2) в худшем случае. Сортировка слиянием (heapsort) в худшем случае работает O (n log n), но реализовать ее немного сложнее, чем quicksort.

Answer 5

Что эти люди, скорее всего, имеют в виду - на работе, мне никогда не придется переопределять процедуру сортировки, почему я должен изучать то, что уже написано?

Я бы сказал, зная, что это полезно для основчто вы узнаете позже.Это считается общим знанием информатики, и изучение любого нового алгоритма поможет вам изучить другие концепции более тщательно.Quicksort может научить вас, как рандомизированные алгоритмы могут привести к лучшим решениям.Сортировка слиянием полезна для изучения рекурсии.Heapsort наглядно демонстрирует компромисс между структурой данных и временем.и т. д. и т. п.

Если ничего другого, их полезно знать для интервью.