O(N log N) – Królowie Sortowania

Najlepsza znana ludzkości optymalna granica wydajnościowa dla klasycznych algorytmów opartych na porównywaniu to O(N log N). Na tym poziomie grają dwa wspaniałe algorytmy z grupy "Dziel i Zwyciężaj" (Divide and Conquer): Quicksort oraz Mergesort.

1. Sortowanie przez Scalanie (Mergesort)

Logika algorytmu zamyka się w 3 krokach:

1. Rozbij zadaną tablicę dokładnie na dwie połowy.
2. Posortuj pierwszą połowę (wywołując Mergesorta na połówce) i posortuj drugą połowę.
3. Scal (Merge) te dwie mniejsze, posortowane tablice z powrotem w jedną wielką tablicę!

Python

def merge_sort(arr):
    if len(arr) > 1:
        srodek = len(arr) // 2
        lewa = arr[:srodek]
        prawa = arr[srodek:]

        merge_sort(lewa)
        merge_sort(prawa)

        i = j = k = 0

        while i < len(lewa) and j < len(prawa):
            if lewa[i] < prawa[j]:
                arr[k] = lewa[i]
                i += 1
            else:
                arr[k] = prawa[j]
                j += 1
            k += 1

        while i < len(lewa):
            arr[k] = lewa[i]
            i += 1
            k += 1

        while j < len(prawa):
            arr[k] = prawa[j]
            j += 1
            k += 1

C++

#include <iostream>
#include <vector>
using namespace std;

// Funkcja scalająca dwie połówki
void merge(vector<int>& arr, int lewy, int srodek, int prawy) {
    int n1 = srodek - lewy + 1;
    int n2 = prawy - srodek;
    
    // Tymczasowe wektory dla lewej i prawej połówki
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) L[i] = arr[lewy + i];
    for (int j = 0; j < n2; j++) R[j] = arr[srodek + 1 + j];
    
    int i = 0, j = 0, k = lewy;
    
    // Scalanie elementów w odpowiedniej kolejności
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    // Jeśli zostały jakieś elementy po lewej stronie
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    // Jeśli zostały jakieś elementy po prawej stronie
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Główna funkcja wywołująca się rekurencyjnie
void mergesort(vector<int>& arr, int lewy, int prawy) {
    if (lewy >= prawy) return;
    
    int srodek = lewy + (prawy - lewy) / 2;
    
    mergesort(arr, lewy, srodek);
    mergesort(arr, srodek + 1, prawy);
    
    merge(arr, lewy, srodek, prawy);
}

2. Sortowanie Szybkie (Quicksort)

Wymyślone w latach 60, uważane za najszybsze w praktycznym użyciu algorytm sortujący. Działa zupełnie inaczej:

1. Wybiera z tablicy absolutnie losowy element, tzw. Pivot (oś, punkt podparcia).
2. Robi przemeblowanie. Przerzuca wartości tak, by wszystko co jest od pivota mniejsze wylądowało po jego lewej stronie, a większe po jego prawej.
3. Wywołuje się rekurencyjnie dla lewej i prawej połowy.

Oto standardowa partycja algorytmu Lomuto.

Python

def partycja(arr, lewy, prawy):
    pivot = arr[prawy]
    i = lewy - 1
    
    for j in range(lewy, prawy):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
            
    arr[i + 1], arr[prawy] = arr[prawy], arr[i + 1]
    return i + 1

def quicksort(arr, lewy, prawy):
    if lewy < prawy:
        pi = partycja(arr, lewy, prawy)
        quicksort(arr, lewy, pi - 1)
        quicksort(arr, pi + 1, prawy)

C++

#include <iostream>
using namespace std;

int partycja(int arr[], int lewy, int prawy) {
    int pivot = arr[prawy]; 
    int p_index = lewy;     
    
    for (int i = lewy; i < prawy; i++) {
        if (arr[i] <= pivot) {
            swap(arr[i], arr[p_index]);
            p_index++;
        }
    }
    swap(arr[p_index], arr[prawy]);
    return p_index; 
}

void quicksort(int arr[], int lewy, int prawy) {
    if (lewy < prawy) {
        int indeks_pivota = partycja(arr, lewy, prawy);
        quicksort(arr, lewy, indeks_pivota - 1);
        quicksort(arr, indeks_pivota + 1, prawy);
    }
}

[!WARNING] Złożoność Quicksorta O(N log N) jest tylko średnia. Kiedy wywołamy go na już posortowanej tablicy wybierając prawy Pivot, czas degraduje się do bardzo słabego O(N^2).