«Шейкерная» сортировка




шейкерная сортировка c++, шейкер-сортировка с++, сортировка перемешиванием с++, cocktail sort c++

Рассмотрев «пузырьковую» сортировку массива можно перейти к разбору её разновидности — «шейкер»-сортировке. Вы можете встретить несколько её названий : сортировка перемешиванием, пульсирующая сортировка, двунаправленная сортировка «пузырьком».

Внимательно присмотревшись к тому, как проходит сортировка «пузырьком» — можно сказать следующее: часть массива, в котором перестановки элементов уже не происходят (отсортированная часть массива), то эту часть можно исключить из рассмотрения и не обрабатывать на следующих итерациях. Второе, что вы могли заметить — это то, что минимальный (самый «легкий» элемент) при сортировке сразу перемещается в самое начало массива, а «тяжелые» элементы сдвигаются только на одну позицию «вниз». Так массив

шейкерная сортировка c++, шейкер-сортировка с++, сортировка перемешиванием с++, cocktail sort c++

будет отсортирован за один проход вложенным циклом, а для массива

шейкерная сортировка c++, шейкер-сортировка с++, сортировка перемешиванием с++, cocktail sort c++

понадобится три итерации.

шейкерная сортировка c++, шейкер-сортировка с++, сортировка перемешиванием с++, cocktail sort c++
Источник: kvodo.ru

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

Рассмотрим саму функцию в которой происходит «шейкер»-сортировка (двунаправленная сортировка «пузырьком») — строки 14-31. Благодаря переменным leftMark и rightMark участок массива, который подлежит сортировке будет сужаться с каждым шагом цикла. Это положительно скажется на времени работы программы. А благодаря двум вложенным циклам for — за одну итерацию внешнего цикла минимальное и максимальное значения займут свои правильные позиции в массиве.

Результат:

шейкерная сортировка c++, шейкер-сортировка с++, сортировка перемешиванием с++, cocktail sort c++

Как и говорилось, на выполнение сортировки массива по возрастанию понадобилось в два раза меньше итераций внешнего цикла по сравнению с классической «пузырьковой» сортировкой.

Почитайте также о других алгоритмах сортировок данных.

Рассылка новых уроков по программированию:


Согласен получать уведомления от purecodecpp.com на мой e-mail

Дата
Страница
Шейкерная сортировка в С++
Рейтинг
5

«Шейкерная» сортировка: 3 комментария

  1. Зачем в условии while (leftMark <= rightMark) (строка 18) проверка на равенство? Ведь в случае равенства левой и правой границ остался 1 элемент, и для него прохождение лишней итерации не требуется.

  2. Чем шейкерная сортировка эффективнее? — тем что за одну итерацию внешнего цикла не только наименьший элемент перемещается вниз, но и наибольший — вверх? — дак зато сама итерация стала сложнее.

    Т.е. в худшем случае пузырьковой сортировки было N итераций внешнего цикла, каждая из которых выполняла N-i итераций внутреннего (где i — номер итерации внешнего цикла). Т.е. сложность вычисляется как сумма (N-i) для всех i от 1 до N, т.е. N * (N+1)/2 = 0.5*N^2 + 0.5*N. Асимптотически — это N^2, но формулу пишу такую, т.к. более точная (может быть так у шейкера хоть какое-то преимущество появится?)

    В худшем случае шейкерной сортировки будет выполнено N/2 итераций внешнего цикла (ведь за одну итерацию 2 элемент занимают свои места в отсортированном массиве), а вот внутренний цикл имеет сложность (N-i) * 2. Сложность сортировки — это сумма (N-i)*2 для всех i от 1 до N/2. Опять видим арифметическую прогрессию и считаем сумму как
    N * ((N-1) + (N-N/2))/2 = N * (N-1 + N — N/2)/2 = (1.5*N*N-N)/2 = 0.75*N^2 — N/2.

    Дак вот даже если отбросить анализ при N стремящемся к бесконечности (где сортировки эквиваленты по эффективности), очевидно же, что для небольших значений N «оптимизированный» алгоритм будет работать хуже (по крайней мере в худшем случае).

    Где я сейчас неправильно посчитал? — никогда не понимал всех этих свистоплясок с шейкером.

Добавить комментарий

Код размещайте в тегах: <pre class="lang:c++ decode:true ">YOUR CODE</pre>