Шейкерная сортировка и сортировка выбором ИТ 1 курс 2 сем ЛЭТИ. лабораторная 2. Лабораторная работа Алгоритмы и программы решения задач комбинаторики Алгоритм шейкерной
 Скачать 143.98 Kb.
|
|
Лабораторная работа 2. Алгоритмы и программы решения задач комбинаторики Алгоритм «шейкерной» сортировки Является развитием сортировки пузырьком. Начинается процесс как в «сортировке пузырьком»: выдавливаем максимум в конец массива. После этого идём в обратную сторону, при этом уже переставляем минимум в начало массива. Затем снова производим сортировку в противоположную сторону. Обойдя туда-обратно несколько раз, в итоге заканчиваем процесс, оказавшись в середине списка. Задание. Реализовать алгоритм сортировки (по возрастанию) для n-вектора исходных данных на языке С++ и определить число перестановок элементов вектора (M).  Рисунок 1 – Алгоритм «шейкерной» сортировки. Алгоритм сортировки выбором Алгоритм сортировки (рис. 2) выбором находит в исходном массиве максимальный или минимальный элементы, в зависимости от того, как необходимо сортировать массив, по возрастанию или по убыванию. Если массив должен быть отсортирован по возрастанию, то из исходного массива необходимо выбирать минимальные элементы. Если же массив необходимо отсортировать по убыванию, то выбирать следует максимальные элементы. Допустим необходимо отсортировать массив по возрастанию. В исходном массиве находим минимальный элемент, меняем его местами с первым элементом массива. Уже, из всех элементов массива один элемент стоит на своём месте. Теперь будем рассматривать не отсортированную часть массива, то есть все элементы массива, кроме первого. В неотсортированной части массива опять ищем минимальный элемент. Найденный минимальный элемент меняем местами со вторым элементом массива и т. д. Таким образом, суть алгоритма сортировки выбором сводится к многократному поиску минимального (максимального) элементов в неотсортированной части массива.  Рисунок 2 – Алгоритм сортировки выбором. Задание. Задан алгоритм сортировки выбором и вектор исходных данных S(n). Реализовать алгоритм сортировки (по возрастанию) для вектора исходных данных на языке С++ и определить число перестановок (m) элементов вектора Особенность Элементы вектора для сортировки и размер этого вектора в обоих случаях вводится с клавиатуры. В отчете необходимо предоставить блок-схемы рассматриваемых алгоритмов, их программную реализацию и листинги результатов работы программы. |