Quicksort

Animácia činnosti algoritmu

Quicksort alebo rýchle triedenie je jeden zo 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 vymyslel v roku 1962 Sir Charles Antony Richard Hoare.

Algoritmus

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.

Implementácie

C

//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];
}

Java

public static void quicksort(int[] array, int left, int right){
   if(left < right){ 
       int boundary = left;
       for(int i = left + 1; i < right; i++){ 
           if(array[i] > array[left]){ 
               swap(array, i, ++boundary);
           }
       }
       swap(array, left, boundary);
       quicksort(array, left, boundary);
       quicksort(array, boundary + 1, right);
   }     
}

private static void swap(int[] array, int left, int right){
   int tmp = array[right]; 
   array[right] = array[left];
   array[left] = tmp;
}

C++

void quicksort(int array[], int left, int right){
   if(left < right){ 
       int boundary = left;
       for(int i = left + 1; i < right; i++){ 
           if(array[i] > array[left]){ 
               swap(array, i, ++boundary);
           }
       }
       swap(array, left, boundary);
       quicksort(array, left, boundary);
       quicksort(array, boundary + 1, right);
   }     
}

void swap(int array[], int left, int right){
   int tmp = array[right]; 
   array[right] = array[left];
   array[left] = tmp;         
}

C#

public static void Quicksort(int[] array, int left, int right)
{
    if (left < right)
    {
        int boundary = left;
        for (int i = left + 1; i < right; i++)
        {
            if (array[i] > array[left])
            {
                Swap(array, i, ++boundary);
            }
        }
        Swap(array, left, boundary);
        Quicksort(array, left, boundary);
        Quicksort(array, boundary + 1, right);
    }
}

private static void Swap(int[] array, int left, int right)
{
    int tmp = array[right];
    array[right] = array[left];
    array[left] = tmp;
}

Iné projekty

Commons

• Commons ponúka multimediálne súbory na tému Quicksort