Шейкер сортування в C все, що вам потрібно знати
Всім привіт! Минулої статті ми вивчили пухирцеве сортування. Як ми вже дізналися вона не найкращий вибір для сортування. Але в минулій статті ми також згадали, що деякі алгоритми дещо запозичили у бульбашкового сортування (!) і тому їх почали називати її різновидами. Один з таких різновидів -шейкер сортування.
Що таке шейкер сортування
Ми можемо зробити деякі модифікації в бульбашковому сортуванні, щоб зробити її швидше.
Проблема бульбашкового сортування у тому, що значення осередків масиву повільно займають свої відсортовані позиції (індекси). І це нас наштовхує на спосіб прискорення алгоритму.
Справа в тому, що зараз ми сортуємо масив в одному напрямку, а можемо спробувати по черзі змінювати напрями сортування. Так ми зможемо домогтися, щоб елементи (які далеко від своїх відсортованих позицій) швидко змогли зайняти свої правильні місця.
Такий різновид бульбашкового сортування називається - Шейкер сортування (4 Cocktail sort ). У неї така незвичайна назва, бо коли її за допомогою сортують, масив схожий на коктейль, який намагаються перемішати.
Як створити шейкер сортування в C++
Нижче ви можете побачити реалізацію шейкер сортування:
Давайте розберемо як цей код працює:
За допомогою булевої змінної sort_or_not , яку ми створили в першому рядку і відразу ж привласнили значення true , ми дізнаватися чи змінювали комірки своє значення (за два цикли):
- sort_or_not приймає значення false , якщо результати умов, що знаходяться у рядках 6 та 12 дорівнюють true .
Весь сенс полягає в тому, що за умови циклу do whileнаписано (поки що) sort_or_not == false . Це означає, поки змінюються значення осередків між собою, ми закінчувати сортування не збираємося.
Якщо ж булева змінна sort_or_not за цикл не дорівнювала false , то ми спокійно виходимо з циклу.
Всередині циклу do while ви можете побачити два алгоритми бульбашкового сортування, що по черзі стоять, тільки з різними напрямками сортування (ми це згадали вище).
Як бачите реалізація не така вже й складна, як могла з'явитися на початку. Також цей алгоритм можна зробити швидше, але це нижче.
Як можна покращити шейкер сортування
Ви напевно вже помітили, що найбільший елемент переміщається в кінець масиву (за перший цикл do while), а найменший елемент переміститься вниз на одну комірку.
У наступному циклі все вже станеться навпаки: найменший елемент переміститься на початку масиву, а другий за розмірами елемент переміститься на одну клітинку вгору. Так само буде для елементів, що залишилися.
Це нас наштовхує на думку, що після першого повного проходу циклу кінець масиву більше можна не перевіряти (оскільки там вже буде найбільший елемент), також можна не перевіряти початку масиву після другого повного проходу циклу.
- Тому нижчеу рядку 2:ми створили змінну right , в ній знаходитиметься правий кордон масиву
- Ау рядку 3:створили змінну left , в якій зберігатиметься початок масиву.
Змінну right ми зменшуватимемо на один після першого циклу for (який знаходитьсяу рядках 6 - 11), left ж будемо зменшувати після другого циклу (ну або іншими словами в самому кінці циклу do while ).
Так ми зможемо прискорити алгоритм кілька разів (все залежить від розміру масиву).
Нижче,знаходиться оптимізована версія шейкер сортування: