Які алгоритми сортування має знати Junior Java Developer

Розбираємо 5 ключових

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

Як вимірюється ефективність алгоритмів

Сортування — це алгоритм, а ефективність будь-якого алгоритму вимірюють за допомогою нотації «О» великого. «О» відповідає за кількість простих операцій, які повинен виконати алгоритм, і може вимірювати витрачений час або пам’ять. Наприклад, скільки операцій потрібно зробити, щоби відсортувати масив чисел чи знайти найменше значення. Такий підхід допомагає оцінити, як буде збільшуватися час виконання алгоритму зі зростанням вхідних даних — методу може бути передано масив і з 10, і з 1000 чисел.

Для кожного алгоритму можна оцінювати найгірший, середній та найкращий випадок.

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

Завдання може звучати так:

«Напишіть метод, який сортує числа в несортованому масиві array у зростальному порядку. Потім назвіть часову складність алгоритму».

Алгоритмів сортування — понад 25, але на прикладі розв’язання цього завдання ми розповімо про 5 ключових, рухаючись від простого до складного та ефективнішого.

Так варіюється складність алгоритмів:

O(n) — лінійна складність означає, кожен елемент масиву потрібно буде перевірити 1 раз.
O(n log n) — кількість перевірок дорівнюватиме логарифму кількості елементів масиву.
O(n^2) — кількість перевірок дорівнюватиме n^2, де n — кількість елементів.

1. Сортування бульбашкою

Найпростішим і водночас найгіршим рішенням буде сортування бульбашкою. Поки масив не буде відсортований (isSorted = false), ми проходимося по всіх елементах та порівнюємо поточне та наступне значення (array[i] >array[i+1]). Якщо поточний елемент більший за наступний, їх потрібно поміняти місцями. temp присвоюється значення array[i], потім array[i] присвоюється array[i+1], а array[i+1] дорівнює temp. Метод проходить по всьому масиву доти, поки найменші значення не виявляться на його початку.

Чим більший вхідний масив, тим більше проходів по ньому потрібно зробити, а це означає, що час порівняння елементів збільшиться.

public void bubbleSort(int[] array) {
    boolean isSorted = false;
    int temp;
    while(!isSorted) {
        isSorted = true;
        for (int i = 0; i < array.length-1; i++) {
            if (array[i] > array[i + 1]) {
                temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                isSorted = false;
            }
        }
    }
}

У гіршому та середньому випадку таке сортування має найгіршу часову складність серед усіх способів — квадратичну O(n^2).

2. Сортування вибором

Для нього потрібно пройтися по всьому масиву і знайти найменший елемент, а потім пересунути його в стартову позицію. Водночас стартова позиція для наступного проходу зсунеться праворуч.

public static void selectionSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int position = i;
        int min = array[i];
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < min) {
                position = j;
                min = array[j];
            }
        }
        array[position] = array[i];
        array[i] = min;
    }
}

Це сортування вважається нестійким, якщо застосовується до складніших структур даних. Наприклад, якщо ви сортуєте масив об’єктів, такий алгоритм змінить порядок об’єктів з однаковим ключем, але різними іншими значеннями. Оцінка за часом у гіршому та середньому значенні дорівнюватиме O(n^2).

3. Сортування вставками

Для сортування вставками нам потрібно зміщувати елементи праворуч, поки вони не будуть між найближчими найбільшими та найменшими значеннями (рядки 5–9).

public void insertSort(int[] array) {
    for (int left = 0; left < array.length; left++) {
        int key = array[left];
        int i = left - 1;
        for (; i >= 0; i--) {
            if (key < array[i]) {
                array[i + 1] = array[i];
            } else {
                break;
            }
        }
        array[i + 1] = key;
    }
}

На відміну від попереднього способу, це сортування не змінює порядок однакових елементів і є стійким. Складність для гіршого та середнього випадку — O(n^2), але найкращий — O(n), оскільки не потрібно буде йти по масиву вдруге.

4. Сортування перемішуванням

Суть цього сортування полягає в тому, що ми йдемо масивом не лише до кінця (рядки 8–12), а й до початку (рядки 21–26). В обох блоках коду ми, по суті, використовуємо сортування бульбашкою.

void cocktailSort(int[] array) {
    boolean isSwapped = true;
    int start = 0;
    int end = array.length;

    while (isSwapped == true) {
        isSwapped = false;
        for (int i = start; i < end - 1; ++i) {
            if (array[i] > array[i + 1]) {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                isSwapped = true;
            }
        }
        if (isSwapped == false)
            break;
        isSwapped = false;
        end = end - 1;

        for (int i = end - 1; i >= start; i--) {
            if (array[i] > array[i + 1]) {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                isSwapped = true;
            }
        }
        start = start + 1;
    }
}

У найгіршому й найкращому випадку оцінка часу буде також O(n^2), але для кращого — лінійною O(n).

5. Швидке сортування

Найефективніший спосіб для цього завдання — швидке сортування. Спочатку ми вибираємо один елемент, а потім сортуємо решту відносно нього.

public void quickSort(int[] array, int low, int high) {
    if (low >= high) return;
    int pivot = array[low + (high - low) / 2];

    int i = low, j = high;
    while (i <= j) {
        while (array[i] < pivot) {
            i++;
        }
        while (array[j] > pivot) {
            j--;
        }

        if (i <= j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
    }

    if (low < j) quickSort(array, low, j);
    if (high > i) quickSort(array, i, high);
}

У рядку 3 позначимо елемент посередині масиву як опорний. Потім розбиваємо масив на дві частини (рядки 5–12). Переміщуємо всі елементи з меншими значеннями до опорного елемента, з більшими після (рядки 14–20). За допомогою рекурсі застосовуємо метод до значень праворуч і ліворуч (рядки 22–23). Якщо сортувати вже нічого, метод завершиться в другому рядку. Найгірший випадок досі дорівнює O(n^2), але середній значно кращий — O(n log n).

Знати алгоритми сортування потрібно, щоби розуміти, як влаштовані методи класу Arrays, колекції та Stream API. Алгоритми з різною «O» найкраще демонструють, як оцінюється складність методів. Якщо ви зрозумієте різницю між квадратичною та лінійною складністю, то перестанете писати надлишкові цикли та знатимете, де взяти готову реалізацію.

Автор: Біденко Дмитро

Поділитися: