Сортировка перемешиванием
Сортировка перемешиванием (Шейкерная сортировка) (англ. Cocktail sort) - разновидность пузырьковой сортировки.
Алгоритм
Анализируя метод пузырьковой сортировки можно отметить два обстоятельства.
Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.
Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.
Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.
Реализация сортировки перемешиванием на С++
03 | void cocktail_sort( Iterator first, Iterator last ) |
05 | for( --last; first < last; --last, ++first ) |
07 | for( Iterator i = first; i < last; ++i ) |
08 | if ( *(i + 1) first; --i ) |
10 | std::iter_swap( i, i - 1 ); |
Вывод по сортировке перемешиванием
Лучший случай для этой сортировки - отсортированный массив (О(n)), худший - отсортированный в обратном порядке (O(n²)).