Domů » Informatika » Algoritmus » Řadící algoritmus » Quick sort (rychlé řazení)

Quick sort (rychlé řazení)

Quick sort je řadící algoritmus, inspirovaný přístupem „rozděl a panuj“ (divide et impera). V roce 1962 jej popsal sir Charles Antony Richard Hoare.

Ve vstupním poli je nejprve zvolen jeden prvek, tzv. pivot, který slouží jako etalon pro prvky zbývající. Zbytek pole je poté přeuspořádán tak, aby byly prvky menší než pivot před pivotem a prvky větší nebo rovné pivotu za pivotem. Algoritmus je potom rekurzivně spuštěn na obou těchto částech.

Algoritmus quick sort lze naimplementovat různým způsobem – ovlivňovat lze způsob selekce pivotu, stabilitu a velikost potřebné pomocné paměti. Algoritmus není přirozený a je efektivní až pro větší pole, proto se pro ta malá zpravidla nevyužívá.

Jeho teoretická asymptotická složitost je sice v nejhorším případě až € O(n^2) €, ale při vhodné volbě pivotu může klesnout až na obvyklejší hodnotu € O(n \cdot \log n) €.

Základní kroky algoritmu:

  • volba pivotu
  • přesun prvků menších než pivot před něj
  • přesun prvků větších nebo rovných pivotu za něj
  • spuštění algoritmu na část pole obsahující menší prvky
  • spuštění algoritmu na část pole obsahující větší prvky (prvky stejné jako pivot je možné přeskočit)

Implementace (Java)

kód v jazyce Java - Zobrazit

  1. /**
  2.  * Implementace algoritmu quick sort.
  3.  * @param input pole k seřazení
  4.  * @author Vojtěch Hordějčuk
  5.  */
  6. public static <T extends Comparable<? super T>> void quickSort(final T[] input)
  7. {
  8.   quickSort(input, 0, input.length - 1);
  9. }
  10.  
  11. /**
  12.  * Hlavní metoda pro rekurzivní řazení.
  13.  * @param input pole k seřazení
  14.  * @param iStart dolní index řazené části pole
  15.  * @param iEnd horní index řazené části pole
  16.  */
  17. private static <T extends Comparable<? super T>> void quickSort(final T[] input, final int iStart, final int iEnd)
  18. {
  19.   if (iEnd > iStart)
  20.   {
  21.     // přesuň pivot a ostatní prvky na správné místo
  22.     final int iPivot = split(input, iStart, iEnd);
  23.  
  24.     // seřaď část pole menší než pivot
  25.     quickSort(input, iStart, iPivot - 1);
  26.  
  27.     // seřaď část pole větší než pivot
  28.     quickSort(input, iPivot + 1, iEnd);
  29.   }
  30. }
  31.  
  32. /**
  33.  * Metoda pro přesun pivotu a ostatních prvků na správné místo. Přesune prvky
  34.  * menší než pivot před něj a prvky větší než pivot za něj.
  35.  * @param input vstupní pole k rozdělení
  36.  * @param iStart dolní index řazené části pole
  37.  * @param iEnd horní index řazené části pole
  38.  * @return nový index pivotu
  39.  */
  40. private static <T extends Comparable<? super T>> int split(final T[] input, final int iStart, final int iEnd)
  41. {
  42.   // zvol index pivotu (zde je to prostřední prvek)
  43.   // používá se i první prvek, náhodný prvek nebo zjednodušený medián
  44.  
  45.   final int iPivot = (iStart + iEnd) / 2;
  46.   final T pivot = input[iPivot];
  47.  
  48.   // přesuň pivot na konec
  49.  
  50.   swap(input, iPivot, iEnd);
  51.  
  52.   // začni posupovat od prvního prvku pole
  53.  
  54.   int iTemp = iStart;
  55.  
  56.   for (int i = iStart; i < iEnd; i++)
  57.   {
  58.     if ((input[i]).compareTo(pivot) <= 0)
  59.     {
  60.       // aktuální prvek je menší než pivot, prohoď je
  61.  
  62.       swap(input, i, iTemp);
  63.  
  64.       // pokračuj na další prvek
  65.  
  66.       iTemp++;
  67.     }
  68.   }
  69.  
  70.   // přesuň pivot zpět doprostřed
  71.  
  72.   swap(input, iEnd, iTemp);
  73.  
  74.   return iTemp;
  75. }
  76.  
  77. /**
  78.  * Metoda pro prohození dvou prvků.
  79.  * @param input vstupní pole
  80.  * @param i1 první index
  81.  * @param i2 druhý index
  82.  */
  83. private static <T extends Comparable<? super T>> void swap(final T[] input, final int i1, final int i2)
  84. {
  85.   final T temp = input[i2];
  86.   input[i2] = input[i1];
  87.   input[i1] = temp;
  88. }