Comments 6
В двусторонней сортировке «Но при этом в 2 раза увеличилось количество сравнений» — вы таки неправы. Не в два, а в полтора: при одновременном поиске максимума и минимума следует выбирать из массива по два элемента, сравнивать их между собой, потом больший сравнивать с максимумом, а меньший с минимумом. Итого 3 сравнения на 2 элемента.
Я точно не уверен, но у сортировки выбором есть одно важное свойство: она сортирует используя минимальное число свопов. По крайней мере я умею доказывать это свойство при условии, что все элементы различны. Выглядит доказательство как-то так: если все элементы различны, то существует ровно одна перестановка элементов, образующая отсортированный порядок, «минимальное число свопов» = «количество элементов» — «количество циклов в этой перестановке», если сортировка выбором делает своп, то количество циклов увеличивается;
Быть может кто-то умеет доказывать/опровергать это в общем случае?
Быть может кто-то умеет доказывать/опровергать это в общем случае?
Всё верно, это общее отличие сортировок данного класса. Поэтому у них, как правило, средняя сложность по времени не отличается от худшей и лучшей. Та же пирамидальная сортировка не имеет ни вырожденных ни удобных случаев и обрабатывает любой массив за O(n log n).
Cycle sort в вопросе минимизации свопов идёт ещё дальше. Дело в том, что в обычной сортировке выбором при свопе один элемент попадает на своё окончательное место, а второй отправляется куда получится. Цикличная сортировка второй элемент отправляет не в освободившееся место в массиве, а в буфер обмена. В этом случае издержки на лишние перезаписи минимальны настолько, насколько вообще это возможно — для всех неопределившихся с местом элементов промежуточная перезапись происходит только в небольшой области памяти — постоянном буфере обмена, а не в самом массиве.
Cycle sort в вопросе минимизации свопов идёт ещё дальше. Дело в том, что в обычной сортировке выбором при свопе один элемент попадает на своё окончательное место, а второй отправляется куда получится. Цикличная сортировка второй элемент отправляет не в освободившееся место в массиве, а в буфер обмена. В этом случае издержки на лишние перезаписи минимальны настолько, насколько вообще это возможно — для всех неопределившихся с местом элементов промежуточная перезапись происходит только в небольшой области памяти — постоянном буфере обмена, а не в самом массиве.
Спасибо за статью! Ещё одна статья с годной подачей принципов сортировки в копилку, будет куда неофитов отсылать для наглядного описания принципов сортировок)
Еще о двусторонней. Под рукой совершенно ничего нет, так что предположение может быть и неверным вообще.
Если мы сравнили элемент j+1 с j и нашли, что j+1 максимальный, то j тогда «первый после максимального»? «Предмаксимальный», условно говоря. Если при прохождении по массиву сохранять индекс и при нахождении максимума ставить предмаксимальный перед максимумом, а элемент, который стоял на этой позиции, свопать с ним, то мы сортируем по два элемента за раз, прав ли я?
Если мы сравнили элемент j+1 с j и нашли, что j+1 максимальный, то j тогда «первый после максимального»? «Предмаксимальный», условно говоря. Если при прохождении по массиву сохранять индекс и при нахождении максимума ставить предмаксимальный перед максимумом, а элемент, который стоял на этой позиции, свопать с ним, то мы сортируем по два элемента за раз, прав ли я?
Sign up to leave a comment.
Сортировки выбором