Повний гайд з алгоритмів сортування на Java для новачків
Частина 1. Сортуємо вставкою, вибором, бульбашкою і не тільки
У цій статті розбираємо алгоритми сортування Java та приклади їхньої реалізації. Зокрема з'ясовуємо, що таке алгоритми сортування, навіщо вони потрібні та як вибрати відповідний алгоритм для конкретного завдання.
Що таке алгоритм сортування
Алгоритм сортування — це набір інструкцій, який приймає на вході алгоритм або список і впорядковує його елементи в зазначеному порядку.
Сортування зазвичай проводять у числовому або алфавітному порядку, за зростанням (0–9 / А–Я) або за спаданням (9–0 / Я–А).
Ось як це виглядає:
- Невідсортований масив:
а л г о р и т м - Сортування масиву за зростанням:
а г и л м о р т - Сортування масиву за спаданням:
т р о м л и г а
Навіщо потрібні алгоритми сортування і якими вони бувають
Алгоритми — це інструкції для оптимального розв'язання проблем. Конкретно в алгоритмів сортування є різні практичні застосування. Наприклад, вони спрощують роботу з пошуком, базами та структурами даних.
Алгоритми сортування поділяють на категорії за кількома факторами:
- Кількість необхідних перестановок або інверсій.
- Кількість порівнянь.
- Наявність рекурсії.
- Стабільність (елементи з одним і тим самим значенням будуть розташовані у відсортованому масиві в тому самому порядку відносно один одного, що й у вихідному).
- Обсяг додаткової пам'яті. Додаткова пам'ять — це пам'ять крім пам'яті для вхідних даних. Вона використовується для зберігання проміжних даних і виражається у величинах від O(1) до O(n)).
Як вибрати відповідний алгоритм сортування
Щоби вибрати алгоритм сортування, потрібно поставити собі кілька запитань:
- Який розмір структури даних, що сортується?
- Скільки пам'яті доступно?
- Чи потрібно розширювати структуру?
Тобто вам потрібно визначити вимоги та розглянути обмеження використовуваної системи.
Поширені алгоритми сортування
Нижче розглянемо поширені методи сортування масиву на Java для різної часової складності.
Часова складність показує, наскільки впливає кількість вхідних даних на час виконання алгоритму.
Джерело: Big-O Complexity Chart
O(n2):
- сортування вставкою Java;
- сортування вибором Java;
- сортування бульбашкою Java.
O(n log n):
- сортування злиттям Java;
- пірамідальне сортування Java;
- швидке сортування Java.
- сортування Шелла на Java.
O(n+K):
- сортування підрахунком Java.
Також існує сортування перестановкою, за якого алгоритм послідовно генерує перестановки вхідних даних, доки не знайде відсортовану. Це найменш ефективний алгоритм, який тільки можна собі уявити. Його часова складність у найгіршому випадку становить O(∞), оскільки цей алгоритм не має верхньої межі, тому розбирати детально ми його не будемо.
Нижче розбираємо першу частину цього списку ↓
Сортування вставкою Java
Сортування вставкою — це простий алгоритм сортування для масивів з невеликою кількістю елементів.
Масив віртуально розділяється на відсортовану і невідсортовану частини. Потім елементи з відсортованої частини переміщуються на необхідну позицію у відсортованій частині.
Алгоритм сортування вставкою Java
Щоби впорядкувати масив розміром N за зростанням методом вставки, потрібно провести ітерацію масивом і порівняти поточний елемент (ключ) із попереднім. Якщо ключовий елемент менший за попередника, то порівняти його з елементами, розташованими перед попередником. Перемістити великі елементи на одну позицію вгору, щоб створити місце для елемента, який переставляється.
Приклад: сортування вставкою Java
Примітка. Усі методи сортування масиву в цій статті вміщені в пакет sorting і успадковують інтерфейс SortingMethod, що визначений в окремому класі. Код класу SortingMethod і класу, що демонструє результати роботи методів, ви знайдете наприкінці статті.
package sorting;
// Java class implementing Insertion Sort
public class InsertionSort implements SortingMethod {
// Sorts an array
public void sort(int array[]){
// Iterate through elements
for ( int i = 1; i < array.length; i++){
// Assign the key
int key = array[i];
int j = i - 1;
// Place the element before all greater elements
while (j >= 0 && array[j] > key){
array[j+1] = array[j];
j--;
}
array[j+1] = key;
}
}
}
Характеристики сортування вставкою
Часова складність: O(n2)
Додатковий простір: O(1)
Ефективна для малих значень даних. Є адаптивною, тобто підходить також для наборів даних, які вже частково відсортовані.
Сортування вибором Java
Сортування вибором — це простий і ефективний алгоритм сортування, який на кожній ітерації обирає найменший (або найбільший) елемент із невідсортованої частини масиву/списку і переміщує його у відсортовану.
Алгоритм сортування вибором Java
Щоби відсортувати масив методом сортування вибором, потрібно ітеративно обирати найменший або найбільший елемент із невідсортованого підмасиву та міняти його місцями з першим елементом із невідсортованого підмасиву. Повторювати цей процес для кожного елемента з невідсортованого підмасиву, поки не буде відсортовано весь масив.
Приклад: сортування вибором Java
package sorting;
// Java class implementing Insertion Sort
public class SelectionSort implements SortingMethod {
// Sorts an array
public void sort(int array[]){
int len = array.length;
// Iterate through elements
for ( int i = 0; i < len - 1; i++){
// Find the smallest element in the unsorted part
int i_smallest = i;
for (int j = i+1; j < len; j++){
if (array[j] < array[i_smallest])
i_smallest = j;
}
/* Swap the smallest element with the first element
of the unsorted subarray*/
int tmp = array[i_smallest];
array[i_smallest] = array[i];
array[i] = tmp;
}
}
}
Характеристики сортування вибором
Часова складність: O(n2), тому що використовуються два цикли:
- для вибору елементів з масиву по одному = O(n);
- для порівняння обраного елемента з кожним іншим елементом масиву = O(n);
- сукупна складність = O(n) * O(n) = O(n*n) = O(n2).
Додатковий простір: O(1), тому що додаткова пам'ять використовується тільки для зберігання одного значення під час перестановки.
Сортування вибором робить не більше O(n) перестановок і буде корисним, коли запис у пам'ять обходиться дорого.
Сортування бульбашкою Java
Сортування бульбашкою — це найпростіший алгоритм сортування, яке здійснюється шляхом повторюваного переставляння суміжних елементів, якщо вони розташовані не в потрібному порядку.
Цей алгоритм не підходить для великих наборів даних, тому що його складність у середньому і складність у гіршому випадку досить висока.
Алгоритм сортування бульбашкою Java
Провести ітерацію зліва, порівнюючи сусідні елементи та поміщаючи більший із них праворуч. У результаті спочатку буде знайдено найбільший елемент, який потім буде переміщено в крайню праву позицію.
Повторити процес для лівого підмасиву, який ще не відсортовано: знайти в ньому найбільший елемент і помістити його в крайню праву позицію підмасиву. Повторювати процес, поки не будуть відсортовані всі дані.
Приклад: бульбашкове сортування Java
package sorting;
// Java class implementing Bubble Sort (optimized)
public class BubbleSort implements SortingMethod {
public void sort(int array[])
{
int tmp, length = array.length;
boolean swapped;
for (int i = 0; i < length - 1; i++) {
swapped = false;
for (int j = 0; j < length - i - 1; j++) {
if (array[j] > array[j + 1]) {
// Swap left and right
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
swapped = true;
}
}
// If no two elements were swapped,
// exit loop
if (swapped == false)
break;
}
}
}
Характеристики сортування бульбашкою
Часова складність: O(n2)
Додатковий простір: O(1)
Бульбашкове сортування просте для розуміння, і його нескладно реалізувати. Для нього не потрібен додатковий простір, крім тимчасових змінних. Це стабільний алгоритм сортування, тобто елементи з одним і тим самим значенням будуть розташовані в тому самому порядку відносно один одного й у відсортованому масиві.
Водночас сортування бульбашкою дуже повільно обробляє великі набори даних, тому що його часова складність дорівнює O(n2). Крім того, цей алгоритм заснований на порівнянні, що в певних випадках може обмежувати його ефективність.
Сортування злиттям Java
Сортування злиттям — це алгоритм сортування, який ділить масив на підмасиви, сортує кожен з них, а потім об'єднує відсортовані підмасиви, що в результаті дає відсортований масив.
Алгоритм сортування злиттям Java
Рекурсивно розділяти масив на половини, поки його можливо ділити. У результаті в кожному підмасиві залишається тільки один елемент, а такий масив завжди відсортований. Об'єднати відсортовані підмасиви в один відсортований масив.
Приклад: сортування злиттям Java
package sorting;
// Java class implementing Merge Sort
public class MergeSort implements SortingMethod {
// Merges two subarrays of array[].
// First is from leftIndex to midIndex
// Second is from midIndex+1 to rightIndex
void merge(int array[], int leftIndex, int midIndex, int rightIndex)
{
// Find sizes of subarrays
int leftLength = midIndex - leftIndex + 1;
int rightLength = rightIndex - midIndex;
// Create temporary arrays
int leftArray[] = new int[leftLength];
int rightArray[] = new int[rightLength];
// Copy data to temp arrays to process
for (int i = 0; i < leftLength; ++i)
leftArray[i] = array[leftIndex + i];
for (int j = 0; j < rightLength; ++j)
rightArray[j] = array[midIndex + 1 + j];
// Merge temporary arrays
// Initial indices of first and second subarrays
int i = 0, j = 0;
// Initial index of array
int k = leftIndex;
// Traverse arrays choosing elements in order
while (i < leftLength && j < rightLength) {
if (leftArray[i] <= rightArray[j]) {
array[k] = leftArray[i];
i++;
}
else {
array[k] = rightArray[j];
j++;
}
k++;
}
// Copy remaining elements from leftArray and rightArray
while (i < leftLength) {
array[k] = leftArray[i];
i++;
k++;
}
while (j < rightLength) {
array[k] = rightArray[j];
j++;
k++;
}
}
// Sorts array[leftIndex..rightIndex] using merge()
public void mergeSort(int array[], int leftIndex, int rightIndex)
{
if (leftIndex < rightIndex) {
// Find the middle index
int midIndex = leftIndex + (rightIndex - leftIndex) / 2;
// Sort first and second subarrays
mergeSort(array, leftIndex, midIndex);
mergeSort(array, midIndex + 1, rightIndex);
// Merge the sorted subarrays
merge(array, leftIndex, midIndex, rightIndex);
}
}
public void sort(int array[])
{
mergeSort(array, 0, array.length -1);
}
}
Характеристики сортування злиттям
Часова складність: O(N log(N))
Додатковий простір: O(N)
Сортування злиттям застосовується з такою метою:
- сортування великих наборів даних — завдяки тому, що гарантована складність у гіршому випадку дорівнює O(n log n);
- зовнішнє сортування — коли набір даних для сортування занадто великий і не поміщається в пам'ять;
- користувацьке сортування — сортування злиттям можна адаптувати для різних випадків розподілу вхідних даних, наприклад, для частково відсортованих, майже відсортованих або повністю несортованих даних;
- підрахунок кількості інверсій.
Пірамідальне сортування Java
Пірамідальне сортування — це метод сортування на основі порівняння, який використовує структуру даних двійкової купи.
Це сортування нагадує сортування вибором. Спочатку визначається мінімальний елемент і поміщається на початок. Той самий процес повторюється для решти елементів.
Алгоритм пірамідального сортування Java
- створити купу із заданого вхідного масиву;
- повторювати наступні кроки, поки розмір купи не стане рівним одиниці:
- • поміняти місцями кореневий елемент купи (який є найбільшим елементом) з останнім елементом купи;
- • видалити останній елемент купи (який тепер перебуває на правильній позиції);
- • підняти решту елементів купи.
- відсортований масив створюється шляхом зміни порядку елементів у вхідному масиві.
Приклад: пірамідальне сортування Java
package sorting;
// Java class implementing Heap Sort
public class HeapSort implements SortingMethod {
// Sorts using heap sort
public void sort(int array[])
{
int length = array.length;
// Build heap
for (int i = length / 2 - 1; i >= 0; i--)
heapify(array, length, i);
// Extract elements from heap one by one
for (int i = length - 1; i > 0; i--) {
// Move current root to the final position
int tmp = array[0];
array[0] = array[i];
array[i] = tmp;
// Call heapify for the reduced heap
heapify(array, i, 0);
}
}
// Makes a heap
void heapify(int array[], int length, int i)
{
int greatest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
// If left child is greater than the root
if (l < length && array[l] > array[greatest])
greatest = l;
// If right child is greater than the greatest
if (r < length && array[r] > array[greatest])
greatest = r;
// If the greatest is not root
if (greatest != i) {
int tmp = array[i];
array[i] = array[greatest];
array[greatest] = tmp;
// Recursively heapify the sub-tree
heapify(array, length, greatest);
}
}
}
Характеристики пірамідального сортування
Часова складність: O(n log n)
Додатковий простір: O(1)
Пірамідальне сортування виконується «на місці». Його типова реалізація нестабільна, але її можна зробити такою. Воно приблизно у 2–3 рази повільніше за швидке.
Для пірамідального сортування використовується мінімальний обсяг пам'яті. Воно просте для розуміння, оскільки в ньому не використовуються просунуті концепції, наприклад, рекурсія. Водночас пірамідальне сортування нестабільне, оскільки порядок елементів відносно один одного може змінитися. Крім того, воно не зовсім ефективне для обробки дуже складних даних.
Код для демонстрації часу сортування
Створіть папку sorting і помістіть у неї файли з кодом усіх наведених вище класів (наприклад, код класу MergeSort — у файл MergeSort.java тощо).
Створіть у цій же папці файл SortingMethod.java з наведеним нижче кодом:
package sorting;
// Java class declaring SortingMethod interface
interface SortingMethod {
// Sorts an array
public void sort(int array[]);
}
У тій самій папці створіть файл SortingDemo.java з таким кодом:
package sorting;
// Java class demonstrating different sorting methods
public class SortingDemo {
// Prints an array
static void printArray(int array[])
{
int n = array.length;
for (int i = 0; i < n; ++i)
System.out.print(array[i] + " ");
System.out.println();
}
// Main method
public static void main(String args[])
{
System.out.println();
System.out.println("* Array sorting demo *");
System.out.println();
// Declare the array of sorting method instances
SortingMethod sortingMethods[] = {
new InsertionSort(),
new SelectionSort(),
new BubbleSort(),
new MergeSort() ,
new HeapSort(),
new BogoSort()
};
// Demonstrate that methods work
for (int i = 0; i < sortingMethods.length; i++){
System.out.println(sortingMethods[i].getClass().toString());
// Declare the initial array
int array[] = { 9, 8, 10, 3, 4 };
// Show initial array
System.out.print("Initial array: ");
printArray(array);
// Store startTime
double startTime = System.nanoTime();
// Sort the array and show its new state
sortingMethods[i].sort(array);
// Measure method execution time
double endTime = System.nanoTime();
double duration = (endTime - startTime) / 1000000;
System.out.print("Resulting array: ");
printArray(array);
System.out.println("Execution time, ms: " + duration);
System.out.println();
}
}
}
Для компіляції відкрийте командний рядок і перейдіть до каталогу, в якому знаходиться папка sorting (до її батьківського каталогу).
Для компіляції всіх файлів запустіть команду:
javac sorting/*.java
І нарешті, запустіть демо:
java sorting.SortingDemo
Результат:
Другу частину гайду по алгоритмам сортування на Java від robot_dreams читайте тут.
