Условимся, что сортировка должна выполняться "на том же месте", т.е. без заведения второго массива такого же размера.
Сортировка методом прямого включениясостоит в том, что каждый элемент массива вставляется на свое место, при этом все прочие элементы сдвигаются, освобождая место для вставляемого элемента:
FOR I:=2 TO n DO
BEGIN
x := a[I];
включение х на свое место среди a[1]…a[n]
END;
Такой алгоритм легко реализовать:
FOR i := 2 TO n DO
BEGIN
x := a[i]; a[0] := x; j := i;
WHILE (x<a[j-1]) DO
BEGIN
a[j] := a[j-1];
DEC(j)
END;
a[j] : = x
END;
Увы, этот алгоритм весьма неэффективен – приходится "двигать" большие объемы данных.
Метод прямого перебора (его чаще всего самостоятельно изобретают начинающие программисты) работает лучше: в нем меняются местами пары элементов массива и общее число "передвижек" оказывается значительно меньшим:
FOR i := 1 TO n-1 DO
BEGIN
k := минимальный элемент среди a[i] … a[n];
поменять местами a[i] и a[k]
END;
Программируется метод прямого перебора с помощью двух вложенных циклов:
FOR I := 1 TO n-1 DO
BEGIN
k := I; x : = a[I];
FOR j := I+1 TO n DO
IF a[j]<x THEN
BEGIN
k := j;
x := a[k]
END;
a[k] := a [I];
a[I] := x
END;
Сортировка файлов, требующая рекурсии, будет рассмотрена на следующей лекции.
