Алгоритми сортування та O-нотація

Теорія: Велике O нотація

Велике O нотація (O-нотація) — це математичний спосіб опису асимптотичної поведінки функцій. У комп'ютерних науках вона використовується для опису часової складності алгоритмів у найгіршому випадку.

Основні типи складності:

• O(1) - константна складність (найкраща)
• O(log n) - логарифмічна складність
• O(n) - лінійна складність
• O(n log n) - лінійно-логарифмічна складність
• O(n²) - квадратична складність
• O(2ⁿ) - експоненційна складність (найгірша)

O-нотація допомагає порівнювати ефективність алгоритмів незалежно від апаратного забезпечення та конкретних деталей реалізації.

Сортування бульбашкою (Bubble Sort)

Алгоритм порівнює сусідні елементи і міняє їх місцями, якщо вони розташовані в неправильному порядку. Процес повторюється доти, доки масив не буде відсортований.

Складність: O(n²) у найгіршому та середньому випадку, O(n) у найкращому випадку.

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Обмін елементів
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

Сортування вибором (Selection Sort)

Алгоритм знаходить мінімальний елемент у невідсортованій частині масиву і поміщає його на початок. Потім процес повторюється для решти масиву.

Складність: O(n²) у всіх випадках.

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        // Знаходження мінімального елемента
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        
        // Обмін знайденого мінімального елемента з першим елементом
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

Візуалізація сортування

Тест з алгоритмів сортування