4.1.1. Пусть -- целые числа. Требуется
построить массив , содержащий те же
числа, для которого .
Решение. Удобно считать, что числа и представляют собой начальное и конечное значения массива x. Требование <<a и b содержат одни и те же числа>> будет заведомо выполнено, если в процессе работы мы ограничимся перестановками элементов x.
k := 0; {k наименьших элементов массива установлены на свои места} while k <> n do begin | s := k + 1; t := k + 1; | {x[s] - наименьший среди x[k+1]...x[t] } | while t<>n do begin | | t := t + 1; | | if x[t] < x[s] then begin | | | s := t; | | end; | end; | {x[s] - наименьший среди x[k+1]..x[n] } | ... переставить x[s] и x[k+1]; | k := k + 1; end;`
4.1.2. Дать другое решение задачи сортировки, использующее
инвариант << первые k элементов упорядочены>> ().
k:=1 {первые k элементов упорядочены} while k <> n do begin | t := k+1; | {k+1-ый элемент продвигается к началу, пока не займет | надлежащего места, t - его текущий номер} | while (t > 1) and (x[t] < x[t-1]) do begin | | ... поменять x[t-1] и x[t]; | | t := t - 1; | end; end;`
Замечание. Дефект программы: при ложном выражении (t>1) проверка требует несуществующего значения x[0].
Оба предложенных решения требуют числа действий, пропорционального . Существуют более эффективные алгоритмы.