Какой алгоитм сортировки выбрать?

Question

[redq]

Есть три массива: 1.массив из случайных чисел 2. частично отсортированный массив 3. отсортированный массив.
Какой алгоритм сортировки (Selection sort / bubble sort / insertion sort) будет наиболее выгоден для каждого из массивов и почему?

Насколько я понимаю, для массива из случайных чисел будет выгоднее применить selection sort.
Для частично отсортированного массива подойдет как selection sort, так и insertion sort.
А для отсортированного массива лучшим будет insertion sort.

Прав ли я?

Comments

[GlazOtca]

Масло масляное. Что вы собираетесь отсортировать в уже отсортированном массиве?

[redq]

GlazOtca, Откуда компьютеру знать, отсортирован массив или нет? Чтобы это узнать нужно пройти весь алгоритм сортировки. Например сложность insertion sort на отсортированном массиве будет O(n), а selection sort O(n^2). Вот мне и нужно подобрать оптимальный алгоритм для каждого из массивов

[Квазиморд Сидорович]

Откуда компьютеру знать, отсортирован массив или нет?

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

[redq]

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

Answer 1

[dmshar]

Ну так вы же сами ответили на свой вопрос. В любом учебнике по теории алгоритмов есть информация по каждому из вами перечисленных (и другим) алгоритмам сортировки, в котором читателю рассказывают, какую вычислительную сложность имеет каждый из алгоритмов для лучшего (все уже отсортировано), среднего и худшего случаев.
Другое дело, что применять эти знания можно не при сортировке конкретного массива, а когда вы знаете, что вам надо часто сортировать массив, и как правило (или просто - чаще) ваш массив уже будет отсортированным, частично, отсортированным и т.д. (Так очень часто бывает при решении конкретных прикладных задач).
А для конкретного массива, не зная заранее что за данные приходят на вход, ничего конкретного сказать нельзя. Поэтому в таком случае ориентируются на "средний" случай.

Comments

[dmshar]

Dmitrii, Ну, как вариант. Хотя, если у вас миллионов 10 записей, то все-же лучше положиться на удачу, чем запускать процедуру рандомизации.

[dmshar]

Да, я и написал в ответе - вопрос имеет смысл не для отдельного акта сортировки, а при условии, что задача повторяема.
Ну например - вы ведете реестр жителей города с населением 10М человек, причем надо его поддерживать в отсортированном порядке. Ежедневно в городе регистрируется 100 новых жителей и 100 жителей снимается с регистрации. Понятно, что данные у вас всегда "почти отсортированы", и даже если за день вдруг "понаедет" 10К человек - для данного приложения лучше всегда использовать тот алгоритм, который дает лучшие результаты для лучшего случая.
И другая задача - у вас ежедневно поступают данные со всех населенных пунктов страны - от мегаполисов до глухого хутора - с данными по заболеваемости COVID за день. Данные приходят в произвольный момент времени (т.е. в произвольном, неповторяемом порядке), но для отчета вам почему-то надо их представить в отсортированном виде. Вот для такого приложения надо ориентироваться на "средний" показатель.
А если сортировка проводится единожды - то лучше "ничего не трогать" и полагаться на удачу.