Selection Sort

Pseudocode

func Selection(s []int) {
	for i := 0; i < len(s); i++ {
		min := s[i]
		for j := i + 1; j < len(s); j++ {
			if s[j] < min {
				min = s[j]
			}
		}
		s[i] = min
	}
}

Relation to Heapsort

Heapsort is just a selection sort backed by a heap rather than array

Properties

Worst Time	Average Time	Best Time	Worst Space	Average Space	Stability	Adaptive
$\theta (N^2)$	$\theta (N^2)$	$\theta (N)$	$\theta (1)$	$\theta (1)$	Not Stable	Not Adaptive

References

• Selection sort - Wikipedia
• Algorithms (4th ed). Robert Sedgewick, Kevin Wayne
• Introduction to Algorithms (4th ed). Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
• Сортировка выбором - Алгоритмика
• 29.2 Selection Sort & Heapsort | CS61B Textbook