Odd-even sort

O(n²)

Odd-even sort (bubble sort vhodný pro paralelizaci) střídá porovnávání lichých sousedních dvojic (1-2, 3-4, …) a sudých dvojic (0-1, 2-3, …) a prohazuje ty ve špatném pořadí. Opakuje, dokud celé kolo neudělá žádné prohození. Pevné nezávislé dvojice se hodí pro paralelní hardware, i když je pořád O(n²).

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Porovnej každou lichou dvojici (pozice 1-2, 3-4, …) a prohoď, když je ve špatném pořadí.
  2. Porovnej každou sudou dvojici (pozice 0-1, 2-3, …) a prohoď, když je ve špatném pořadí.
  3. Každé kolo může spustit všechna porovnání dvojic nezávisle — výhoda při paralelizaci.
  4. Opakuj, dokud celé kolo neudělá žádné prohození.

Pseudokód

1oddEvenSort(a):                     # O(n²)2  sorted ← false3  while not sorted:4    sorted ← true5    for i = 1, 3, 5, … while i+1 < n:   # odd pairs6      if a[i] > a[i+1]: swap; sorted ← false7    for i = 0, 2, 4, … while i+1 < n:   # even pairs8      if a[i] > a[i+1]: swap; sorted ← false