Лабораторная работа №7 (4 часа).

Лабораторная работа №7 (4 часа).

Сортировки

Общие задания

1. Реализовать сортировку прямым выбором

а) Рассмотреть информацию по методу прямого выбора.

Алгоритм прямого выбора является одним из распространенных в силу своей простоты. Сначала из N элементов выбирается минимальный элемент. Далее 1-ый и найденный минимальный элементы меняются местами. Затем среди оставшихся (N - 1) элементов от 2 до N выбирается минимальный и меняется местами с элементом, стоящим на 2 месте и т.д. Так продолжается до тех пор, пока весь массив не будет отсортирован. Последний раз минимум выбирается из двух элементов, стоящих на (N - 1) и N-ом месте соответственно, и наименьший из них ставится на (N - 1) место.

Поясним принцип на примере:

Пусть дан массив А из 8-ми элементов: 21 46 48 19 14 43 29 21

1 проход.Просматриваем элементы с 1-го по N. Ищем минимальный.

21 46 48 19 14 43 29 21 min = 14, N_min = 5

Меняем местами 1-ый и 5-тый элементы.

14 46 48 19 21 43 29 21

2 проход.Просматриваем элементы со 2-го по N. Ищем минимальный.

14 46 48 19 21 43 29 21 min = 19, N_min = 4

Меняем местами 2-ой и 4-тый элементы.

14 19 48 46 21 43 29 21

3 проход.Просматриваем элементы с 3-го по N. Ищем минимальный.

14 19 48 46 21 43 29 21 min = 21, N_min = 5

Меняем местами 3-ий и 5-тый элементы.

14 19 21 46 48 43 29 21

И т.д.

Сортировка выполнена.

б) Ознакомиться с демонстрацией сортировки прямым выбором (с помощью демопрограммы)

Выбираем пункт 2.Метод прямого выбора.

Затем выбираем пункт Меню -> Изменить N (ставим значение 8-10). Затем снова Меню -> Новый массив.

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

в) Изучить укрупненную блок-схему метода прямого выбора:

г) Написать программу, реализующую алгоритм прямого выбора на языке Pascal с выводом промежуточных этапов сортировки на экран и подсчетом количества сравнений и перестановок.

2. Реализовать сортировку обменами (метод пузырька)

а) Рассмотреть информацию по методу пузырька.

На первом проходе соседние элементы сравниваются, и если элементы не упорядочены, они меняются местами, в результате чего самый меньший элемент переставляется на первое место. За второй проход самый меньший из оставшихся (сравнение идет между (N - 1) элементами) перемещается на второе место и так до тех пор, пока массив не окажется отсортированным. Алгоритм называют пузырьковой сортировкой, потому что на каждом шаге наименьший элемент неотсортированной части подобно пузырьку газа в воде всплывает вверх, т.е. в начало массива.

Поясним принцип на примере:

Пусть дан массив А из 8-ми элементов: 30 17 47 17 6 23 13 48

1 проход. Просматриваем элементы с N-го по 1 парами.

30 17 47 17 6 23 1348…

30 17 47 17 6 2313 48 - меняем местами 23 и 13…

30 17 47 17 6 13 23 48…

30 17 47 17 613 23 48…

30 17 47 176 13 23 48 - меняем местами 17 и 6…

30 17 47 6 17 13 23 48…

30 17 476 17 13 23 48 - меняем местами 47 и 6…

30 17 6 47 17 13 23 48…

30 176 47 17 13 23 48 - меняем местами 17 и 6…

30 6 17 47 17 13 23 48 …

306 17 47 17 13 23 48 - меняем местами 30 и 6…

6 30 17 47 17 13 23 48.

В результате минимальный элемент 6, из интервала от 1 до N, оказывается на первом месте.

2 проход. Просматриваем элементы с N-го по 2 парами.

В результате минимальный элемент 13, из интервала от 2 до N, оказывается на втором месте.

6 13 30 17 47 17 23 48.

3 проход. Просматриваем элементы с N-го по 3 парами.

В результате минимальный элемент 17, из интервала от 3 до N, оказывается на третьем месте.

6 13 17 30 17 47 23 48.

4 проход. Просматриваем элементы с N-го по 4 парами.

В результате минимальный элемент 17, из интервала от 4 до N, оказывается на четвертом месте.

6 13 17 17 30 23 47 48.

5 проход. Просматриваем элементы с N-го по 5 парами.

В результате минимальный элемент 23, из интервала от 5 до N, оказывается на пятом месте.

6 13 17 17 23 30 47 48.

6 проход. Просматриваем элементы с N-го по 6 парами.

В результате минимальный элемент 30, из интервала от 6 до N, оказывается на шестом месте.

6 13 17 17 23 30 47 48.

7 проход. Просматриваем элементы с N-го по 7 парами.

В результате минимальный элемент 47, из интервала от 7 до N, оказывается на седьмом месте.

6 13 17 17 23 30 47 48.

12 Следующая ⇒