Quicksort

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie
Animácia činnosti algoritmu

Quicksort alebo rýchle triedenie je jeden z najrýchlejších známych triediacich algoritmov založených na porovnávaní prvkov. Jeho priemerná doba výpočtu je najlepšia zo všetkých podobných algoritmov (O(n.log(n))). Algoritmus je aj veľmi jednoduchý. Nevýhodou je, že pri výnimočne nevhodnom tvare vstupných dát môže byť časová a pamäťová náročnosť tohto algoritmu až O(n²).

Algoritmus[upraviť | upraviť zdroj]

Základnou myšlienkou quicksortu je rozdelenie triedenej postupnosti čísel na dve približne rovnaké časti. V jednej časti sú čísla väčšie a v druhej menšie ako istá zvolená hodnota, ktorá sa nazýva pivot. Ak je táto hodnota zvolená dobre, sú obe časti približne rovnako veľké. Ak budú obe časti samostatne roztriedené, je roztriedené i celé pole. Obe časti sa potom rekurzívne triedia rovnakým spôsobom.

Najväčším problémom celého algoritmu je voľba pivotu. Ak sa podarí zvoliť číslo blízke mediánu triedenej časti poľa, je algoritmus najrýchlejší. Ak nie, je jeho pamäťová a časová náročnosť vyššia ako pri všetkých ostatných algoritmoch.

//Quicksort the array
void quicksort(int* array, int left, int right)
{
    if(left >= right)
        return;
 
    int index = partition(array, left, right);
    quicksort(array, left, index - 1);
    quicksort(array, index + 1, right);
}
 
//Partition the array into two halves and return the
//index about which the array is partitioned
int partition(int* array, int left, int right)
{
    //Makes the leftmost element a good pivot,
    //specifically the median of medians
    findMedianOfMedians(array, left, right);
    int pivotIndex = left, pivotValue = array[pivotIndex], index = left, i;
 
    swap(array, pivotIndex, right);
    for(i = left; i < right; i++)
    {
        if(array[i] < pivotValue)
        {
            swap(array, i, index);
            index += 1;
        }
    }
    swap(array, right, index);
 
    return index;
}
 
//Computes the median of each group of 5 elements and stores
//it as the first element of the group. Recursively does this
//till there is only one group and hence only one Median
int findMedianOfMedians(int* array, int left, int right)
{
    if(left == right)
        return array[left];
 
    int i, shift = 1;
    while(shift <= (right - left))
    {
        for(i = left; i <= right; i+=shift*5)
        {
            int endIndex = (i + shift*5 - 1 < right) ? i + shift*5 - 1 : right;
            int medianIndex = findMedianIndex(array, i, endIndex, shift);
 
            swap(array, i, medianIndex);
        }
        shift *= 5;
    }
 
    return array[left];
}
 
//Find the index of the Median of the elements
//of array that occur at every "shift" positions.
int findMedianIndex(int* array, int left, int right, int shift)
{
    int i, groups = (right - left)/shift + 1, k = left + groups/2*shift;
    for(i = left; i <= k; i+= shift)
    {
        int minIndex = i, minValue = array[minIndex], j;
        for(j = i; j <= right; j+=shift)
            if(array[j] < minValue)
            {
                minIndex = j;
                minValue = array[minIndex];
            }
        swap(array, i, minIndex);
    }
 
    return k;
}
 
//Swap integer values by array indexes
void swap(int * array, int a, int b)
{
    array[a] -= array[b];
    array[b] += array[a];
    array[a] = array[b] - array[a];
}

Iné projekty[upraviť | upraviť zdroj]