Сортировка методом прямого включения

Сортировка методом прямого включения работает со списком не­упорядоченных чисел (обычно называемых клю­чами), сортируя их в порядке возрастания или убывания. Это делается примерно так же, как большинство игроков упорядочивают сданные им карты, под­нимая каждый раз по одной карте. Покажем работу общей процедуры на примере следующего неотсортированного списка из восьми целых чисел:

27 412 71 81 59 14 273 87,

который надо отсортировать по возрастанию.

Отсортированный список создается заново; вначале он пуст. На каж­дой итерации первое число неотсортированного списка удаляется из него и помещается на соответствующее ему место в отсортированном списке. Для этого отсортированный список просматривается, начиная с наименьшего числа, до тех пор, пока не находят соответствующее место для нового числа, т. е. пока все отсортированные числа с меньшими значениями не окажутся впереди него, а все числа с большими значениями — после него. Другими словами новое число неотсортированного списка включается (устанавливается в соответствующее место) в отсортированный список. Следующая последовательность списков показывает, как это делается:

Итерация 0

Неотсортированный 412 71 81 59 14 273 87

Отсортированный 27

Итерация 1

Неотсортированный 412 71 81 59 14 273 87

Отсортированный 27 412 Включение 412 в отсортированный

список на соответствующее место

Итерация 2

Неотсортированный 71 81 59 14 273 87

Отсортированный 27 71 412 Включение 71

Итерация 3

Неотсортированный 81 59 14 273 87

Осортированный 27 71 81 412 Включение 81

Итерация 4

Неотсортированный 59 14 273 87

Отсортированный 27 59 71 81 412 Включение 59

Итерация 5

Неотсортированный 14 273 87

Отсортированный 14 27 59 71 81 412 Включение 14

Итерация 6

Неотсортированный 273 87

Отсортированный 14 27 59 71 81 273 412 Включение 273

Итерация 7

Неотсортированный 87

Отсортированный 14 27 59 71 81 87 273 412 Включение 87

В данном алгоритме присутствуют два списка последовательностей, что естественно отрицательно сказывается на использование памяти. Другими словами для сортировки списка из N элементов необходимо задействовать 2N ячеек памяти. Поэтому, целесообразнее пользоваться методом прямого включения, который работает с одним списком последовательности. Рассмотрим его также на примере.

Допустим надо отсортировать последовательность из 10 чисел:

10, 20, 5, 45, 12, 2, 46, 48, 23, 32

Укрупненно алгоритм может быть представлен следующим образом: вначале некоторому числу R присваивается второй элемент последовательности, который сравнивается с первым и располагается с ним в порядке возрастания, затем выбирается третий элемент присваивается числу R и сортируется с первыми двумя в порядке возрастания. Эта операция продолжается до тех пор, пока не дойдет очередь до последнего элемента.

Блок схема этого алгоритма представлена на рис.6.1.

Рис.6.1. Блок схема алгоритма сортировки прямым включением.

Текст программы на языке Турбо-Бейсик может быть записан следующим образом:

CLS

DIM I(10)

DATA 10, 20, 5, 45, 12, 2, 46, 48, 23, 32

READ I(1), I(2), I(3), I(4), I(5), I(6), I(7), I(8), I(9), I(10)

FOR n = 1 TO 10: PRINT I(n);: NEXT n: PRINT

J = 1

5 R = I(J)

L = J - 1

9 IF R <= I(L) AND L >= 1 THEN

I(L + 1) = I(L): L = L - 1: GOTO 9

ELSE

I(L + 1) = R

J = J + 1

IF J <= 10 THEN

GOTO 5

ELSE

FOR n = 1 TO 10: PRINT I(n);: NEXT n

END IF

END IF

В представленном алгоритме заводится только один список, и переорга­низация чисел производится в старом списке.