QuickSort

Základní myšlenkou Quicksortu je rozdělení řazené posloupnosti čísel na dvě přibližně stejné části. V jedné části jsou čísla větší a ve druhé menší, než nějaká zvolená hodnota - pivot. Pokud je tato hodnota zvolena dobře, jsou obě části přibližně stejně velké. Pokud budou obě části samostatně seřazeny, je seřazené i celé pole. Obě části se pak rekurzivně řadí stejným způsobem.

Volba pivota je problémem celého algoritmu. Přirozenou metodou volby pivota je medián z daných hodnot. Nemusí to být však příliš efektivní. Existuje mnoho dalších způsobů jak zvolit pivota (Náhodný prvek, medián z několika hodnot, atd.

Asymptotická složitost QuickSortu je O(n log n). Záleží však hodně právě na volbě pivota. Při nevhodné volbě se lze složitostí přiblížit až k O(n²)

static void QuickSort(int npole[],int l,int p)
{
    int pivot = npole[(l+p)/2];
    int pom,i,j;
    i=l;
    j=p;
    do{
        while(npole[i]<pivot) i++;
        while(npole[j]>pivot) j--;
        if(i<=j)
        {
            pom = npole[i];
            npole[i] = npole[j];
            npole[j] = pom;
            i++;
            j--;
        }
    }while(i<j);
    if(j>l) QuickSort(npole,l,j);
    if(i<p) QuickSort(npole,i,p);
}