#algorithm #sorting
#алгоритм #сортировка
Вопрос:
Недавно я работаю над анализом синхронизации базовых алгоритмов сортировки в C #, следуя этой книге. На странице 55 автор вкратце упоминает, что.
Сортировка по выбору является наиболее эффективным из алгоритмов, за которым следуют пузырьковая сортировка и сортировка по вставке
но на самом деле сортировка по выбору занимает больше времени, чем вставка и пузырьковая сортировка в лучшем, нормальном и наихудшем случаях. Даже эта онлайн-визуализация алгоритма показывает, что сортировка по выборке занимает больше времени.
Мой вопрос в том, насколько эффективна сортировка по выбору по сравнению со вставкой и пузырьковой сортировкой?
Комментарии:
1. Наиболее эффективна в чем? Алгоритмы можно сравнивать по времени, сложности и использованию памяти. Обычно вам нужно заменить одно на другое.
2. en.wikipedia.org/wiki/Sorting_algorithm
3. автор @ScottChamberlain упомянул о временной сложности.
4. В реальной жизни это зависит от относительных затрат на чтение, запись и сравнения. Временная сложность квадратична для всех трех.
5. @Steve Я проверил это, но запутался в упоминании инструкции в книге.
Ответ №1:
Я думаю, вы слишком обобщили утверждение автора.
Говоря об относительной эффективности, автор книги сравнивает алгоритмы при очень специфических обстоятельствах:
- Он сравнивает сроки своих конкретных реализаций,
- Он сравнивает время на своем конкретном оборудовании
- Он сравнивает время для рандомизированного набора данных (в отличие от страницы анимации, которая предоставляет четыре варианта)
Измеряя время в этих конкретных обстоятельствах, автор приходит к выводу, что его реализация сортировки по выборке является самой быстрой среди трех реализаций, когда на его конкретном оборудовании сортируются 10000 элементов, выбранных случайным образом. Это единственное утверждение, которое он может обоснованно выдвинуть. В частности, утверждение о том, что сортировка по выбору каким-то образом является наиболее эффективной из трех, является слишком общим для эксперимента автора.
Причина, по которой эксперимент автора привел к ранжированию, которое он показал, скорее всего, заключается в удобстве алгоритмов для кэширования.
Сортировка по выборке большую часть времени выполняет чтение в одном направлении, и большинство ее операций — это чтение. Сортировка по вставке, с другой стороны, требует много записей. Сортировка пузырьками также большую часть времени выполняется в том же направлении, но при этом операции записи смешиваются с операциями чтения и выполняется больше операций записи, чем при сортировке по выбору. Короче говоря, авторская реализация сортировки по выделениям представляется наиболее оптимизированной из трех алгоритмов для аппаратного обеспечения автора
Комментарии:
1. автору следовало бы упомянуть об этом, потому что в основном новички в C #, читающие эту книгу, принимают это утверждение неправильно или наоборот.
2. 2-й пункт, автор сравнивает время рандомизации данных, при котором сортировка по выборке выполняется быстрее, но в реальности сортировка по вставке работает быстрее со случайными данными? согласно моему анализу? Я прав?
3. @MuhammadQasimAshraf Вам нужно много данных (сотни или тысячи записей), чтобы начали проявляться эффекты кэширования. Для небольших случайных наборов данных сортировка по вставке может быть быстрее. Но для больших наборов сортировка по выбору начинает выигрывать из-за ее относительно лучшего удобства для кэша. Конечно, размеры данных в десять тысяч случайных записей выходят далеко за пределы диапазона, в котором сортировка по вставке или выбору должна использоваться на практике.
Ответ №2:
Я не думаю, что сортировка по выбору намного эффективнее всех алгоритмов сортировки, но она эффективнее, чем сортировка пузырьками, но я сомневаюсь в сортировке по вставке
поскольку сортировка по выбору выполняет сортировку на месте, она удаляет минимальный элемент из оставшейся части списка, а затем вставляет его в конец отсортированных на данный момент значений.
Сортировка по вставке сканирует только те элементы, которые необходимы для сортировки элемента, но сортировка по выбору должна сканировать весь список для сортировки любого элемента.
Смотрите этот пример сортировки по выборке
64 25 12 22 11
Сначала он находит минимальный элемент в этом списке, это 11
теперь меняются местами 11 и 64
11 25 12 22 64
далее находит минимум в 25 12 22 64, что равно 12
итак, теперь список равен 11 12 25 22 64, этот процесс продолжается
где, как и при сортировке по вставке
64 25 12 22 11
сначала проверяется, что 25 меньше 64
25 64 12 22 11
12 64 25 22 11
12 25 64 22 11
12 22 64 25 11
12 22 25 64 11
11 22 25 64 12
11 12 25 64 22
11 12 22 64 25
11 12 22 25 64
Временная сложность пузырька, выделения и вставки равна O (n2)
Сортировка по выбору хорошо работает для списков меньшего размера, но я думаю, что они не работают для больших списков, для больших списков слияние / быстрая сортировка являются лучшими
Надеюсь, это поможет