Algoritmi → Sortiranje → Brzo sortiranje (Quick Sort)

Brzo sortiranje (Quick Sort)

Razdvajanje oko pivota

Za pivot uzimamo poslednji element dela niza a[l..d]. Promenljiva i pokazuje kraj dela sa elementima manjim od pivota. Prolazimo sa j od l do d − 1: kada je a[j] < pivot, proširujemo „mali“ deo (i++) i menjamo a[i] i a[j]. Na kraju pivot stavljamo odmah iza malog dela – na poziciju i + 1, koja je njegovo konačno mesto.

Posle razdvajanja broj 5 je na mestu na kome će biti i u sortiranom nizu. Ostaje da se sortiraju delovi 2 4 3 i 9 8 7 – istim postupkom.

Kompletan program

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

vector<int> a;

// razdvaja a[l..d] oko pivota a[d]; vraća konačnu poziciju pivota
int razdvoji(int l, int d) {
    int pivot = a[d];
    int i = l - 1;                    // a[l..i] su elementi manji od pivota
    for (int j = l; j < d; j++) {
        if (a[j] < pivot) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[d]);             // pivot ide iza manjih elemenata
    return i + 1;
}

void quickSort(int l, int d) {
    if (l >= d) return;               // 0 ili 1 element: već sortirano
    int p = razdvoji(l, d);
    quickSort(l, p - 1);              // levo od pivota
    quickSort(p + 1, d);              // desno od pivota
}

int main() {
    int n;
    cin >> n;
    a.resize(n);
    for (int &x : a) cin >> x;
    quickSort(0, n - 1);
    for (int x : a) cout << x << " ";
    cout << endl;
    return 0;
}

Za opadajući poredak u funkciji razdvoji uslov se menja u a[j] > pivot.

Video: brzo sortiranje

Postupak razdvajanja i rekurzivnih poziva prikazan je u videu.

Složenost i izbor pivota

Ako pivot svaki put podeli niz na dva približno jednaka dela, nivoa rekurzije ima oko log₂ n, a na svakom nivou se obradi n elemenata – ukupno O(n log n).

Najgori slučaj nastaje kada je pivot uvek najmanji ili najveći element – na primer kada je niz već sortiran, a za pivot uzimamo poslednji element. Tada se od n elemenata odvaja samo pivot, pa je složenost O(n²), a dubina rekurzije n.

Rešenje: pivot biramo slučajno. Pre razdvajanja zamenimo slučajno izabrani element sa poslednjim:

#include <cstdlib>
// na početku funkcije razdvoji(l, d):
int r = l + rand() % (d - l + 1);   // slučajna pozicija iz [l, d]
swap(a[r], a[d]);                   // ona postaje pivot

Funkcija sort iz C++ biblioteke koristi poboljšano brzo sortiranje koje se, ako rekurzija postane preduboka, prebacuje na drugi algoritam – zato nikada ne radi O(n²).

Primena: k-ti najmanji element

Posle razdvajanja pivot je na svojoj konačnoj poziciji p. Ako tražimo element koji bi u sortiranom nizu bio na poziciji k, dovoljno je nastaviti samo u jednom delu: levo ako je k < p, desno ako je k > p. Ovaj algoritam (quickselect) u proseku radi O(n). U C++ postoji gotova funkcija nth_element.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje