Задача урока — трассировать и программировать сортировку выбором на Pascal в обоих направлениях.
Что значит упорядочить
Неубывающий порядок означает, что каждый следующий элемент не меньше предыдущего. Невозрастающий порядок означает, что каждый следующий элемент не больше предыдущего. Равные соседние значения допустимы в обоих определениях.
Механика выбора
Для массива из N элементов внешний цикл сортировки выбором выполняет N - 1 шагов. На шаге i экстремум ищут только в ещё не отсортированной части от i до последнего индекса. После обмена элемент на позиции i уже находится на окончательном месте. Вложенный цикл поиска и операция обмена должны быть разделены: обмен выполняют после полного просмотра хвоста. Для невозрастающего порядка на очередное место выбирают максимум, для неубывающего — минимум.
В Pascal при индексах от 1 до N внешний цикл можно записать for i := 1 to N - 1 do, а поиск вести for j := i + 1 to N do. Обмен удобно выполнить через временную переменную.
Самодостаточный пример на Pascal
Ниже одна программа сортирует четыре числа по невозрастанию. Функция MaxIndex возвращает индекс максимума хвоста, а процедура Swap получает обмениваемые элементы через параметры var.
pascal
program SelectionDemo;
const N = 4;
type TData = array[1..N] of integer;
var A: TData;
i: integer;
procedure Swap(var left, right: integer);
var tmp: integer;
begin
tmp := left;
left := right;
right := tmp
end;
function MaxIndex(const values: TData; first: integer): integer;
var j, best: integer;
begin
best := first;
for j := first + 1 to N do
if values[j] > values[best] then best := j;
MaxIndex := best
end;