сортировка — изучение основных понятий (8/21)

Сортировка записей: основные понятия

Сортировка — перестановка исходных элементов, удовлетворяющая заданному строгому порядку. Корректный результат одновременно упорядочен и содержит ровно те же записи.

Сортировка выбором

Для позиции k найдите лучшую запись в хвосте k..n−1 и обменяйте её с a[k]. Инвариант: после шага префикс содержит лучшие элементы в окончательном порядке.

Свойства

Алгоритм выполняет n(n−1)/2 сравнений, не более n−1 обменов, работает in-place и в обычной форме не гарантирует устойчивость.

Pascal

Реализуйте Better и SelectionSort; record обменивается целиком. Следите за границами k и j.