розглянувши “пузырьковую” сортировку массива можно перейти к разбору её разновидности – “шейкер”-сортировке. Вы можете встретить несколько её названий : сортировка перемешиванием, пульсирующая сортировка, двунаправленная сортировка “пузырьком”.
Внимательно присмотревшись к тому, как проходит сортировка “пузырьком” – можна сказати наступне: часть массива, в котором перестановки элементов уже не происходят (отсортированная часть массива), то эту часть можно исключить из рассмотрения и не обрабатывать на следующих итерациях. Друге, что вы могли заметить – это то, что минимальный (самый “легкий” элемент) при сортировке сразу перемещается в самое начало массива, а “тяжелые” элементы сдвигаются только на одну позицию “вниз”. так масив
будет отсортирован за один проход вложенным циклом, а для массива
понадобится три итерации.
Тому була придумана більш ефективна форма сортування “пузырьком” -“шейкер”-сортировка. У ній межі тієї частини масиву в якій є перестановки, сужаются. Плюс – внутренние циклы проходят по массиву то в одну, то в другую сторону, піднімаючи найлегший елемент вгору і опускаючи найважчий елемент в самий низ за одну ітерацію зовнішнього циклу. Набирайте код:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #include <iostream> using namespace std; //ф-ция для обмена значений ячеек void swapEl(int *arr, int i) { int buff; buff = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = buff; } //ф-ция "шейкер"-сортировки void myShakerSort(int *arr, int size) { int leftMark = 1; int rightMark = size - 1; while (leftMark <= rightMark) { for (int i = rightMark; i >= leftMark; i--) if (arr[i - 1] > arr[i]) swapEl(arr, i); leftMark++; for (int i = leftMark; i <= rightMark; i++) if (arr[i - 1] > arr[i]) swapEl(arr, i); rightMark--; cout << "\nИтерация: " << leftMark - 1; // просмотр количества итераций } } int main() { setlocale(LC_ALL, "rus"); int size = 0; cout << "Размер массива: "; cin >> size; int *A = new int[size]; for (int k = 0; k < size; k++) { A[k] = size - k; // запись значений по убыванию cout << A[k] << " | "; } myShakerSort(A, size); // сортировка cout << "\nМассив после сортировки:\n"; for (int k = 0; k < size; k++) { cout << A[k] << " | "; } cout << endl; return 0; } |
Рассмотрим саму функцию в которой происходит “шейкер”-сортировка (двунаправленная сортировка “пузырьком”) – строки 14-31. завдяки змінним leftMark і RightMark участок массива, который подлежит сортировке будет сужаться с каждым шагом цикла. Це позитивно позначиться на часі роботи програми. А благодаря двум вложенным циклам for – за одну ітерацію зовнішнього циклу мінімальне і максимальне значення займуть свої правильні позиції в масиві.
Результат:
Как и говорилось, на виконання сортування массива по зростанню знадобилося в два рази менше ітерацій зовнішнього циклу в порівнянні з класичною “пузырьковой” сортировкой.
Почитайте також про інших алгоритмах угруповань даних.
Навіщо в умови while (leftMark <= rightMark) (рядок 18) перевірити рівність? Адже в разі рівності лівої і правої меж залишився 1 элемент, і для нього проходження зайвої ітерації не потрібно.
Чим шейкерні сортування ефективніше? – тим що за одну ітерацію зовнішнього циклу не тільки найменший елемент переміщається вниз, але і найбільший – вгору? – дак зате сама ітерація стала складніше.
Тобто,. в гіршому випадку бульбашкового сортування було N ітерацій зовнішнього циклу, кожна з яких виконувала N-i ітерацій внутрішнього (де i – номер ітерації зовнішнього циклу). Тобто,. складність обчислюється як сума (N-я) для всіх i від 1 до N, т.е. N * (N + 1)/2 = 0,5 * N ^ 2 + 0.5*N. асимптотично – це N ^ 2, але формулу пишу таку, т.к. точніша (може бути так у шейкера хоч якусь перевагу з'явиться?)
У гіршому випадку шейкерні сортування буде виконано N / 2 ітерацій зовнішнього циклу (адже за одну ітерацію 2 елемент займають свої місця в відсортованому масиві), а от внутрішній цикл має складність (N-я) * 2. складність сортування – це сума (N-я)*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 “оптимізований” алгоритм буде працювати гірше (по крайней мере в гіршому випадку).
Де я зараз неправильно порахував? – ніколи не розумів всіх цих свістоплясок з шейкером.
Шейкерні сортує майже відсортований масив за O(n)