- Сортировка перемешиванием
-
Сортировка перемешиванием (Шейкерная сортировка) (англ. Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства.
Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.
Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.
Лучший случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).
Наименьшее число сравнений в алгоритме Шейкер-сортировки C=N-1. Это соответствует единственному проходу по упорядоченному массиву (лучший случай)
Код программы на языке программирования С++
#include <vcl.h> #include <conio.h> #include <iostream.h> #pragma hdrstop #pragma argsused // Шейкер-сортировка int main(int argc, TCHAR* argv[]) { const int Count = 10; int TestArr[Count] = {3,1,5,8,1,0,6,4,6,7}; ShakerSort(TestArr,1,Count); ArrayOutput(TestArr,0,Count); return 0; } //Поменять местами i-й и i-1-й элементы массива Arr void Swap(int Arr[], int i) { int temp; //буфер temp = Arr[i]; Arr[i] = Arr[i-1]; Arr[i-1] = temp; } void ShakerSort(int Arr[], int Start, int N) { int Left,Right; //границы сортировки int Last; //место последней перестановки Left=Start; Right = N-1; Last = N-1; do { //Сдвигаем к концу массива "легкие элементы" for (int i =Right; i >= Left; i--) { if (Arr[i-1]>Arr[i]) { Swap(Arr, i); Last = i; //Запомнить место последней перестановки } } Left = Last + 1; //Сдвигаем к началу массива "тяжелые элементы" for (int i =Left; i <= Right; i++) { if (Arr[i-1]>Arr[i]) { Swap(Arr, i); Last = i; //Запомнить место последней перестановки } } Right = Last - 1; } while (Left<=Right); } //Вывод элементов массива на консоль void ArrayOutput(int* Arr, int Start, int N) { for (int i = 0; i < N; i++) { cout << Arr[i] << '\n'; } getch(); }
Трассировка программы
3 1 5 8 1 0 4 6 6 7 3 1 5 8 0 1 4 6 6 7 3 1 5 0 8 1 4 6 6 7 3 1 0 5 8 1 4 6 6 7 3 0 1 5 8 1 4 6 6 7 0 3 1 5 8 1 4 6 6 7 Left=1 0 1 3 5 8 1 4 6 6 7 0 1 3 5 1 8 4 6 6 7 0 1 3 5 1 4 8 6 6 7 0 1 3 5 1 4 6 8 6 7 0 1 3 5 1 4 6 6 8 7 0 1 3 5 1 4 6 6 7 8 Right=8 0 1 3 1 5 4 6 6 7 8 0 1 1 3 5 4 6 6 7 8 Left=3 0 1 1 3 4 5 6 6 7 8 Ссылки
Алгоритмы сортировки Теория Сложность • О-нотация • Отношение порядка • Типы сортировки: Устойчивая • Внутренняя • Внешняя
Алгоритмы Обменные: Пузырьком • Перемешиванием • Гномья • Быстрая • Расчёской • Выбором: Выбором • Пирамидальная • Вставками: Вставками • Шелла • Деревом • Слиянием: Слиянием • Без дополнительной памяти • Без сравнений: Подсчётом • Поразрядная • Блочная • Гибридные: Introsort • Timsort • Прочее: Топологическая • Сети • Непрактичные: Bogosort • Stooge sort • Глупая • Блинная
Категория:- Алгоритмы сортировки
Wikimedia Foundation. 2010.