Quick sort

z Wikipédie, slobodnej encyklopédie
Jump to navigation Jump to search

Quicksort je veľmi rýchly nestabilný triediaci algoritmus založený na princípe Divide et Impera (rozdeľuj a panuj) s asymptotickou zložitosťou O(n^2) a s očakávanou zložitosťou O(n * log n). Algoritmus vymyslel v roku 1962 Sir Charles Antony Richard Hoare.

Algoritmus[upraviť | upraviť zdroj]

Kódy algoritmov v rôznych jazykoch:

Java[upraviť | upraviť zdroj]

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++[upraviť | upraviť zdroj]

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#[upraviť | upraviť zdroj]

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