Quick sort

O(n log n)

Quick sort zvolí pivot a rozdělí pole tak, aby menší hodnoty skončily vlevo od něj a větší vpravo — pivot tím dostane své konečné místo. Pak rekurzivně zpracuje obě strany. V průměru je O(n log n) a šetrný k cache, proto je výchozím řazením v mnoha jazycích; špatný pivot ho ale může zhoršit na O(n²).

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Zvol pivot (zde poslední prvek rozsahu).
  2. Projdi rozsah a každou hodnotu menší než pivot prohoď na levou stranu.
  3. Prohoď pivot na hranici — teď je na svém konečném místě.
  4. Rekurzivně zpracuj části vlevo a vpravo od pivota.

Pseudokód

1quickSort(a, lo, hi):               # O(n log n) avg2  if lo ≥ hi: return3  pivot ← a[hi]4  i ← lo5  for j from lo to hi-1:6    if a[j] < pivot:                 # smaller ones to the left7      swap(a[i], a[j]); i ← i + 18  swap(a[i], a[hi])                  # pivot lands in place9  quickSort(a, lo, i-1); quickSort(a, i+1, hi)