Повний гайд з алгоритмів сортування на Java для новачків | robot_dreams
Для відстеження статусу замовлення - авторизуйтесь
Введіть код, який був надісланий на пошту Введіть код із SMS, який був надісланий на номер
 
Код дійсний протягом 2 хвилин Код з SMS дійсний протягом 2 хвилин
Ви впевнені, що хочете вийти?
Сеанс завершено
На головну
Повний гайд з алгоритмів сортування на Java для новачків

Повний гайд з алгоритмів сортування на 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

  • створити купу із заданого вхідного масиву;
  • повторювати наступні кроки, поки розмір купи не стане рівним одиниці:
    1. • поміняти місцями кореневий елемент купи (який є найбільшим елементом) з останнім елементом купи;
    2. • видалити останній елемент купи (який тепер перебуває на правильній позиції);
    3. • підняти решту елементів купи.
  • відсортований масив створюється шляхом зміни порядку елементів у вхідному масиві.

Приклад: пірамідальне сортування 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 читайте тут.

Ще статті
У два рази більше натхнення та інформації на другій онлайн-конференції від robot_dreams
Експертки про те, як оцінюють кандидатів на нетехнічних інтерв’ю