Впровадження алгоритму швидкого сортування в Java

1. Огляд

У цьому посібнику ми детально дослідимо алгоритм QuickSort, зосередившись на його реалізації Java.

Ми також обговоримо його переваги та недоліки, а потім проаналізуємо його складність у часі.

2. Алгоритм швидкого сортування

Quicksort - це алгоритм сортування, який використовує принцип поділу і перемоги. Він має середню складність O (n log n), і це один з найбільш часто використовуваних алгоритмів сортування, особливо для великих обсягів даних.

Важливо пам’ятати, що Quicksort не є стабільним алгоритмом. Стабільний алгоритм сортування - це алгоритм, коли елементи з однаковими значеннями відображаються в тому самому порядку у відсортованому виведенні, як і у списку введення.

Список введення розділений на два підсписки елементом, який називається pivot; один підсписок з елементами, меншими за опорну точку, та інший із елементами, більшими від базової точки. Цей процес повторюється для кожного підсписку.

Нарешті, всі відсортовані підсписки об’єднуються, утворюючи кінцевий результат.

2.1. Кроки алгоритму

  1. Ми вибираємо елемент зі списку, який називається опорним. За його допомогою ми поділимо список на два підсписки.
  2. Ми впорядковуємо всі елементи навколо стержня - ті, що мають менші значення, розміщуються перед ним, а всі елементи, більші за стержень після нього. Після цього кроку стовп знаходиться в остаточному положенні. Це важливий крок розділу.
  3. Ми застосовуємо вищезазначені кроки рекурсивно до обох під-списків ліворуч і праворуч від зведення.

Як ми бачимо, швидке сортування, природно, є рекурсивним алгоритмом, як і будь-який підхід "розділи і владь".

Візьмемо простий приклад, щоб краще зрозуміти цей алгоритм.

Arr[] = {5, 9, 4, 6, 5, 3}
  1. Припустимо, для простоти ми обрали 5 як опору
  2. Спочатку ми помістимо всі елементи менше 5 у перше положення масиву: {3, 4, 5, 6, 5, 9}
  3. Потім ми повторимо це для лівого підмасиву {3,4}, взявши 3 як стержень
  4. Тут немає елементів менше 3
  5. Ми застосовуємо швидку сортування до підмасиву праворуч від зведення, тобто {4}
  6. Цей підмасив складається лише з одного відсортованого елемента
  7. Ми продовжуємо з правою частиною вихідного масиву, {6, 5, 9}, поки не отримаємо остаточний упорядкований масив

2.2. Вибір оптимального повороту

Найважливішим моментом у QuickSort є вибір найкращої опори. Середній елемент, звичайно, найкращий, оскільки він би розділив список на два однакові підсписки.

Але знайти середній елемент із невпорядкованого списку досить складно і трудомістко, тому ми беремо за опору перший елемент, останній елемент, медіану або будь-який інший випадковий елемент.

3. Впровадження в Java

Перший метод - quickSort (), який приймає за параметри масив, що підлягає сортуванню, перший та останній індекс. По-перше, ми перевіряємо індекси і продовжуємо лише за умови, що є ще елементи для сортування.

Ми отримуємо індекс відсортованого зведення і використовуємо його для рекурсивного виклику методу partition () з тими ж параметрами, що і метод quickSort () , але з різними індексами:

public void quickSort(int arr[], int begin, int end) { if (begin < end) { int partitionIndex = partition(arr, begin, end); quickSort(arr, begin, partitionIndex-1); quickSort(arr, partitionIndex+1, end); } }

Продовжимо з методом partition () . Для простоти ця функція приймає останній елемент як опору. Потім перевіряє кожен елемент і замінює його місцями перед зведенням, якщо його значення менше.

До кінця розділення всі елементи менше, ніж півот, знаходяться ліворуч від нього, а всі елементи, більші за півот, знаходяться праворуч від нього. Зворот знаходиться в остаточному відсортованому положенні, і функція повертає це положення:

private int partition(int arr[], int begin, int end) { int pivot = arr[end]; int i = (begin-1); for (int j = begin; j < end; j++) { if (arr[j] <= pivot) { i++; int swapTemp = arr[i]; arr[i] = arr[j]; arr[j] = swapTemp; } } int swapTemp = arr[i+1]; arr[i+1] = arr[end]; arr[end] = swapTemp; return i+1; }

4. Аналіз алгоритму

4.1. Складність часу

У найкращому випадку алгоритм розділить список на два підсписки однакового розміру. Отже, для першої ітерації повного n- великого списку потрібен O (n) . Для сортування решти двох підсписків з n / 2 елементами потрібно по 2 * O (n / 2) кожен. Як результат, алгоритм QuickSort має складність O (n log n) .

У гіршому випадку алгоритм вибере лише один елемент у кожній ітерації, тож O (n) + O (n-1) +… + O (1) , що дорівнює O (n2) .

У середньому QuickSort має складність O (n log n) , що робить його придатним для великих обсягів даних.

4.2. QuickSort проти MergeSort

Давайте обговоримо, в яких випадках нам слід вибрати QuickSort замість MergeSort.

Хоча як Quicksort, так і Mergesort мають середню часову складність O (n log n) , Quicksort є найкращим алгоритмом, оскільки він має O (log (n)) просторову складність. З іншого боку, Mergesort вимагає додаткового сховища O (n) , що робить його досить дорогим для масивів.

Quicksort вимагає доступу до різних індексів для своїх операцій, але цей доступ неможливий безпосередньо у зв’язаних списках, оскільки немає безперервних блоків; тому для доступу до елемента ми маємо перебирати кожен вузол з початку пов'язаного списку. Також Mergesort реалізовано без додаткового місця для LinkedLists.

У такому випадку, як правило, кращим є збільшення накладних витрат для Quicksort та Mergesort.

5. Висновок

Quicksort - це елегантний алгоритм сортування, який дуже корисний у більшості випадків.

Зазвичай це алгоритм "на місці" із середньою часовою складністю O (n log n).

Ще одним цікавим моментом, який слід згадати, є те, що метод Java Arrays.sort () використовує Quicksort для сортування масивів примітивів. Реалізація використовує два стрижні та працює набагато краще, ніж наше просте рішення, тому для виробничого коду зазвичай краще використовувати бібліотечні методи.

Як завжди, код для реалізації цього алгоритму можна знайти в нашому сховищі GitHub.