Bubble sort

O(n²)

Bubble sort prochází pole stále dokola a prohazuje každou dvojici sousedů, kteří jsou ve špatném pořadí. Po každém průchodu „probublá“ největší zbývající hodnota na své konečné místo na konci, takže seřazená část roste zprava. Je jednoduchý a stabilní, ale pomalý — O(n²) — takže slouží spíš k výuce než k praxi.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Porovnej první dva prvky; pokud je levý větší, prohoď je.
  2. Posuň se o krok doprava a porovnej další dvojici; opakuj až na konec neseřazené části.
  3. Po každém průchodu skončí největší neseřazená hodnota na svém konečném místě na konci.
  4. Opakuj průchody, dokud není potřeba žádné prohození — pole je seřazené.

Pseudokód

1bubbleSort(a):                      # O(n²)2  for i from 0 to n-1:3    for j from 0 to n-2-i:4      if a[j] > a[j+1]:             # out of order5        swap(a[j], a[j+1])         # bubble the larger up6    # after pass i, a[n-1-i] is in its final place