Контрольная работа структуры и алгоритмы обработки данных. Контрольная работа. Контрольная работа по предмету Структуры и алгоритмы обработки данных
 Скачать 100.46 Kb.
|
|
В данном способе сортировки произведётся 11 шагов перестановки, на каждом шаге 1 обмен (всего М=3×(12-1)=33 перестановки, так как каждый обмен требует три перестановки). На первом шаге выполняется 11 сравнений, на втором – 10 сравнений, на третьем – 9, на последующих n-1. На 11-ом шаге – одно сравнение. Всего получается С=(11+1)/2)·11=66 сравнений. Ответ: АААВЕЛНННОПХ; 66 сравнений, 33 перестановки. Задание 2. Для набора из 12 символов ФИО студента выполнить вручную шейкерную сортировку. Подсчитать количество необходимых сравнений и перестановок. Определить на каждом шаге в методе шейкерной сортировки левую и правую границы сортируемой части массива (L и R). Решение: Набор символов ФИО: ПЛЕХАНОВААНН Шейкерная сортировка — усовершенствованная разновидность сортировки пузырьком, при которой сортировка производиться в двух направлениях, меняя направление при каждом проходе. Проанализировав алгоритм пузырьковой сортировки, можно заметить: 1. Если при обходе части массива не происходит обмен элементов, то эту часть можно исключить, так как она уже отсортирована; 2. При проходе от конца массива к началу минимальное значение сдвигается на первую позицию, при этом максимальный элемент перемещается только на один индекс вправо. Мы перемещаем минимальный элемент в начало массива, а максимальный - в конец, после этого выбрасываем индексы этих элементов из рабочей области. Таким образом, за каждую итерацию просматриваемая часть массива уменьшается на два элемента. Выполним шейкерную сортировку:
|