Selection sort

O(n²)

Selection sort dělí pole na seřazený začátek a neseřazený zbytek. V každém kole projde neseřazenou část, najde minimum a prohodí ho na hranici. Vždy udělá stejný počet porovnání — O(n²) — ale jen málo prohození (nejvýš n−1), což se hodí, když je zápis drahý.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Projdi neseřazenou část a najdi její nejmenší hodnotu.
  2. Prohoď ji s prvním neseřazeným políčkem.
  3. Seřazená část na začátku se zvětší o jedna.
  4. Opakuj, dokud není celé pole seřazené.

Pseudokód

1selectionSort(a):                   # O(n²)2  for i from 0 to n-1:3    min ← i4    for j from i+1 to n-1:5      if a[j] < a[min]: min ← j      # find the smallest left6    swap(a[i], a[min])               # put it at the front