Структуры и алгоритмы обработки данных

Структуры и алгоритмы обработки данных.

Контрольная работа.

Кузнецова Елена Александровна.

Задание 1. Для набора из 12 символов ФИО студента выполнить вручную сортировку методом прямого выбора (пример см. в лекциях, раздел 2.1). Определить количество необходимых  сравнений и перестановок.

Решение.

Набор символов ФИО: КУЗНЕЦОВАЕЛЕ. 

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

Чтобы сравнивать буквы в наборе, определим их числовые значения в соответствии с алфавитом, пронумеровав их по порядку:

Таблица работы метода прямого выбора:

КУЗНЕЦОВАЕЛЕ

АУЗНЕЦОВКЕЛЕ

АВЗНЕЦОУКЕЛЕ

АВЕНЗЦОУКЕЛЕ

АВЕЕЗЦОУКНЛЕ

АВЕЕЕЦОУКНЛЗ

АВЕЕЕЗОУКНЛЦ

АВЕЕЕЗКУОНЛЦ

АВЕЕЕЗКЛОНУЦ

АВЕЕЕЗКЛНОУЦ

АВЕЕЕЗКЛНОУЦ

АВЕЕЕЗКЛНОУЦ

Красным цветом отмечается текущий минимальный элемент при его поиске. Зеленым цветом отмечаются отсортированные элементы.

Всего шагов (просмотров набора для поиска минимального элемента) производится 11 (на 12-ом шаге ничего делать не нужно, так как остается одна буква). На каждом шаге производится один обмен (всего М=3·11=33 перестановки, так как каждый обмен требует три перестановки). На первом шаге выполняется 11 сравнений, на втором – 10 сравнений, …, на 11-ом шаге – одно сравнение. Всего получается С=(11+1)/2·11=66 сравнений.

Задание 2. Для набора из 12 символов ФИО студента выполнить вручную шейкерную сортировку. Подсчитать количество необходимых сравнений и перестановок. Определить на каждом шаге в методе шейкерной сортировки левую и правую границы сортируемой части массива (L и R).

Решение.

Набор символов ФИО: КУЗНЕЦОВАЕЛЕ. 

Таблица работы шейкерной сортировки:

Синим цветом отмечены пары символов, для которых понадобилась перестановка.

В отсортированный набор (отмечен зелёным цветом) снесены сверху левые и правые “поворотные” символы (АВЕЕЕ и НОУЦ), а также оставшаяся часть массива, в которой перестановки уже не нужны (ЗКЛ).