Швидке сортування - один з кращих методів сортування масивів
Якщо ви програмуєте і ваш код іде далі написання калькулятора, ти ви не раз зіткнетеся або стикалися з необхідністю впорядкувати той чи інший масив даних. Існує безліч способів сортування. У цій статті ми розберемо основні з них і зробимо акцент на швидкій сортуванню.
Поняття швидкого сортування
Швидке сортування - Quick Sort або qsort. За назвою стає зрозуміло, що це і для чого. Але якщо не зрозуміло, то це алгоритм по швидкій сортуванні масиву, алгоритм має ефективність O (n log n) в середньому. Що це означає? Це означає, що середній час роботи алгоритму підвищується по тій же траєкторії, що і графік даної функції. У деяких популярних мовах є вбудовані бібліотеки з цим алгоритмом, а це вже говорить про те, що він украй ефективний. Це такі мови, як Java, C ++, C #.
Алгоритм
Метод швидкого сортування використовує рекурсію і стратегію "Розділяй і володарюй".
1. У масиві шукається якийсь опорний елемент, для простоти краще взяти центральний, але якщо ви хочете попрацювати над оптимізацією, то доведеться спробувати різні варіанти.
2. Зліва від опори шукається елемент більший, ніж опорний, праворуч - менший, ніж опорний, потім міняємо їх місцями. Робимо це, поки максимальний праворуч становить не менше, ніж мінімальний зліва. Таким чином, всі маленькі елементи кидаємо в початок, великі - в кінець.
3. Рекурсивно застосовуємо даний алгоритм до лівої і правої частини нашого алгоритму окремо, потім ще і ще, до досягнення одного елемента або певної кількості елементів. Що ж це за кількість елементів? Є ще один спосіб оптимізувати даний алгоритм. Коли сортируемое частина стає приблизно рівною 8 або 16, то можна обробити її звичайної сортуванням, наприклад бульбашковій. Так ми підвищимо ефективність нашого алгоритму, тому маленькі масиви він обробляє не так швидко, як хотілося б.
Таким чином, буде оброблений та відсортований весь масив. А тепер наочно вивчимо даний алгоритм
Ефективність швидкого сортування
Чи є швидке сортування найшвидшим алгоритмом сортування? Однозначно ні. Зараз з'являється все більше і більше сортувань, на даний момент найшвидша сортування - це Timsort, вона працює вкрай швидко для масивів, спочатку відсортованих по-різному. Але не варто забувати, що метод швидкого сортування є одним з найпростіших в написанні, це дуже важливо, адже, як правило, для рядового проекту потрібно саме просте написання, а не величезний алгоритм, який сам ти й не напишеш. Timsort - теж не самий складний алгоритм, але звання самого простого йому точно не світить.
Реалізація алгоритму
Ну ось ми і дійшли до самого "смачного". Тепер розберемо, як реалізовується даний алгоритм. Як говорилося раніше, він не дуже складний в реалізації, швидше, навіть простий. Але ми все одно повністю розберемо кожну дію нашого коду, щоб ви зрозуміли, як працює швидке сортування.
Наш метод називається quickSort. У ньому запускається основний алгоритм, в який ми передаємо масив, перший і останній його елементи. Запам'ятовуємо в змінні i і k перший і останній елемент сортованого відрізка, щоб не змінювати ці змінні, так як вони нам потрібні. Потім перевіряємо відстань між першим і останнім перевіряється: воно більше або дорівнює одиниці? Якщо ні, значить, ми прийшли до центру і потрібно вийти з сортування цього відрізка, а якщо так, то продовжуємо сортування.
Потім за опорний елемент беремо перший елемент у сортованому відрізку. Наступний цикл робимо до того моменту, поки не дійдемо до центру. У ньому робимо ще два цикли: перший - для лівої частини, а другий - для правої. Їх ми виконуємо, поки є елементи, які підходять під умову, або поки не дійдемо до опорного елемента. Потім, якщо мінімальний елемент все ж праворуч, а максимальний - ліворуч, міняємо їх місцями. Коли цикл закінчується, міняємо перший елемент і опорний, якщо опорний менше. Потім ми рекурсивно робимо наш алгоритм для правого і лівого ділянки масиву і так продовжуємо, поки не дійдемо до відрізка довжиною в 1 елемент. Тоді всі наші рекурсивні алгоритми будуть return, і ми повністю вийдемо з сортування. Також внизу є метод swap - цілком стандартний метод при сортуванні масиву замінами. Щоб кілька разів не писати заміну елементів, пишемо один раз і міняємо елементи в даному масиві.
На закінчення можна сказати, що за співвідношенням "якість-складність" швидке сортування перебуває на лідируючій позиції серед всіх алгоритмів, тому вам варто однозначно взяти метод на замітку і використовувати при необхідності в своїх проектах.
