Pancake sort

O(n²)

Pancake sort smí jen obrátit předponu pole („flip“, jako obracení komínu palačinek obracečkou). V každém kole najde největší neseřazenou hodnotu, otočí ji dopředu a pak ji otočí na konec neseřazené části. Je to spíš hlavolam než praktické řazení — O(n²) porovnání a O(n) otočení.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Najdi největší hodnotu v neseřazené předponě.
  2. Otoč předponu tak, aby se ta hodnota dostala dopředu.
  3. Otoč celou neseřazenou předponu, aby hodnota skončila na svém konečném místě na konci.
  4. Zmenši neseřazenou část o jedna a opakuj.

Pseudokód

1pancakeSort(a):                     # O(n²)2  for size = n down to 2:3    mi ← index of the max in a[0..size-1]4    if mi ≠ size-1:5      flip(a, mi)                    # bring the max to the front6      flip(a, size-1)                # flip it down to its place7  # flip(a, k) reverses a[0..k]