Лабораторная работа № 11. Алгоритмы сортировок методами прямого включения и прямого выбора

(15 неделя, 1 час)

Прямое включение. Такой метод широко используется при игре в карты. Элементы (карты) мысленно делятся на уже “готовую” последовательность а₁,…, а_i-1 и исходную последовательность. При каждом шаге, начиная с i = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i – ный элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

Пример сортировки с помощью прямого включения:

Начальные ключи	44	55	12	42	94	18	06	67
i = 2	44	55	12	42	94	18	06	67
i = 3	12	44	55	42	94	18	06	67
i = 4	12	42	44	55	94	18	06	67
i = 5	12	42	44	55	94	18	06	67
i = 6	12	18	42	44	55	94	06	67
i = 7	06	12	18	42	44	55	94	67
i = 8	06	12	18	42	44	55	67	94

Это процесс сортировки с помощью включения 8-ми случайно выбранных чисел. Алгоритм этой сортировки:

FOR i:=2 to n DO

x: = a[i];

{включение х на соответствующее место среди a[1]… a[i] }

END

       В реальном процессе поиска подходящего места удобно, чередуя сравнения и движения по последовательности, как бы просеивать, т.е. х сравнивается с очередным элементов а_j, а затем либо х вставляется на свободное место, либо а_j сдвигается (передается) вправо и процесс «уходит» влево. Обратите внимание, что процесс просеивания может закончиться при выполнении одного из 2-х условий:

1. Найден элемент а_j с ключом, меньшим чем ключ у х.

2. Достигнут левый конец готовой последовательности.

Procedure StraightInsertion;

Var i, j: index; x: item;

Begin

For i:=2 то n DO

x: = a[i]; a[0]: = x; j: = 1;

WHILE x < a[j – 1] DO a[j]: = a[j – 1]; j: = j – 1; END;

a[j]: = x END

END STRAIGHT INSERTION

 

Индивидуальные задания

Выпишите результаты всех проходов алгоритма сортировки списка с помощью прямого включения

1. (7, 3, 9, 4, 2, 5, 6, 1, 8)

2. (8, 6, 4, 3, 9, 7, 5, 1, 2)

3. (1, 9, 6, 8, 4, 2, 7, 5, 3)

4. (6, 3, 2, 8, 4, 7, 5, 9, 1)

5. (4, 6, 8, 9, 5, 7, 3, 2, 1)

6. (4, 7, 5, 1, 2, 9, 8, 3, 6)

7. (8, 6, 2, 5, 9, 3, 4, 1, 7)

8. (3, 9, 6, 8, 4, 7, 1, 5, 2)

9. (23, 17, 21, 3, 42, 9, 13, 1, 2, 7, 35, 4)

10. (2, 35, 8, 41, 9, 41, 11, 6, 58, 77, 23, 7)

11. (7, 13, 52, 77, 53, 56, 68, 2, 71, 22, 95, 58

12. (51, 50, 52, 94, 15, 25, 38, 68, 15, 44, 84, 25)

13. (81, 79, 64, 23, 38, 64, 92, 26, 24, 37, 8, 41)

14. (49, 10, 66, 3, 64, 36, 54, 49, 19, 1, 82, 77)

15. (88, 49, 17, 22, 19, 45, 96, 64, 28, 53, 29, 35)

16. (1, 36, 49, 27, 77, 60, 11, 42, 50, 66, 57, 44)

17. (6, 97, 35, 91, 92, 21, 84, 57, 59, 17, 10, 67)

18. (9, 5, 43, 76, 34, 20, 52, 39, 87, 51, 47, 1)

19. (43, 82, 28, 32, 9, 24, 35, 75, 85, 63, 52, 34)

20. (16, 52, 83, 84, 62, 91, 20, 37, 81, 22, 30, 26)

 

Прямой выбор. Этот прием основан на следующих принципах:

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом а₁

3. Затем этот процесс повторяется с оставшимися n –1 элементами, n –2 элементами, и т.д. до тех пор, пока не останется один, самый большой элемент.

Процесс работы этим методом с теми же 8-мью ключами, что и таблица 2.1. приведен в таблице 2.2. алгоритм формируется так:

FOR i: = 1 to n – 1 do

присвоить k индекс наименьшего из а[i] … a[n];

поменять местами а[i] и a[k];

end

Применение сортировки с помощью прямого выбора

Начальные ключи	44	55	12	42	94	18	06	67
i = 2	06	55	12	42	94	18	44	67
i = 3	06	12	55	42	94	18	44	67
i = 4	06	12	18	42	94	55	44	67
i = 5	06	12	18	42	94	55	44	67
i = 6	06	12	18	42	44	55	94	67
i = 7	06	12	18	42	44	55	94	67
i = 8	06	12	18	42	44	55	67	94

Такой метод – его называют прямым выбором в некотором смысле противоположен прямому включению. При прямом включении на каждом шаге рассматривается только один очередной элемент   исходной последовательности и все элементы готовой последовательности, среди которых отыскивается точка включения; при прямом выборе для поиска одного элемента с наименьшим ключом просматриваются все элементы исходной последовательности и найденный помещается как очередной элемент в готовую последовательность. Полностью алгоритм прямого выбора приводится в программе 2.3.

PROCEDURE StraightSelection:

VAR i,j,k: intex; x: item;

BEGIN

FOR i: = 1 TO n - 1 DO

k: = i; x: = a[i];

FOR j: = i + 1 TO n DO

IF a[j] < x THEN k: = j; x: = a[k] END

END;

END StraightSelection

 

Прогр. Сортировка с помощью прямого выбора.

 

Индивидуальные задания

Выпишите результаты всех проходов алгоритма сортировки списка с помощью прямого выбора

1. (7, 3, 9, 4, 2, 5, 6, 1, 8)

2. (8, 6, 4, 3, 9, 7, 5, 1, 2)

3. (1, 9, 6, 8, 4, 2, 7, 5, 3)

4. (6, 3, 2, 8, 4, 7, 5, 9, 1)

5. (4, 6, 8, 9, 5, 7, 3, 2, 1)

6. (4, 7, 5, 1, 2, 9, 8, 3, 6)

7. (8, 6, 2, 5, 9, 3, 4, 1, 7)

8. (3, 9, 6, 8, 4, 7, 1, 5, 2)

9. (23, 17, 21, 3, 42, 9, 13, 1, 2, 7, 35, 4)

10. (2, 35, 8, 41, 9, 41, 11, 6, 58, 77, 23, 7)

11. (7, 13, 52, 77, 53, 56, 68, 2, 71, 22, 95, 58

12. (51, 50, 52, 94, 15, 25, 38, 68, 15, 44, 84, 25)

13. (81, 79, 64, 23, 38, 64, 92, 26, 24, 37, 8, 41)

14. (49, 10, 66, 3, 64, 36, 54, 49, 19, 1, 82, 77)

15. (88, 49, 17, 22, 19, 45, 96, 64, 28, 53, 29, 35)

16. (1, 36, 49, 27, 77, 60, 11, 42, 50, 66, 57, 44)

17. (6, 97, 35, 91, 92, 21, 84, 57, 59, 17, 10, 67)

18. (9, 5, 43, 76, 34, 20, 52, 39, 87, 51, 47, 1)

19. (43, 82, 28, 32, 9, 24, 35, 75, 85, 63, 52, 34)

20. (16, 52, 83, 84, 62, 91, 20, 37, 81, 22, 30, 26)