Контрольная работа структуры и алгоритмы обработки данных. Контрольная работа. Контрольная работа по предмету Структуры и алгоритмы обработки данных

• Название: Контрольная работа по предмету Структуры и алгоритмы обработки данных
• Анкор: Контрольная работа структуры и алгоритмы обработки данных
• Дата: 01.04.2022
• Размер: 100.46 Kb.
• Имя файла: Контрольная работа.docx
• Тип: Контрольная работа; #434169
• страница: 5 из 8

Ответ: ААЕАЛНОВХНПН

Задание 5. Для набора из 12 символов ФИО студента выполнить вручную сортировку методом Хоара.

Решение:

Набор символов ФИО: ПЛЕХАНОВААНН

Быстрая сортировка — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

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

Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:

1. разбиение массива относительно опорного элемента;

2. рекурсивная сортировка каждой части массива.

Правила сортировки массива:

1) Первую сортировку проводим по двум крайним символам, причём:

Красный цвет — опорный символ.

Жёлтый цвет — символ сравниваемый с опорным.

2) Если опорный символ оказался больше сравниваемого, то они меняются местами. Сравниваемый символ становится отсортированным и обозначается зелёным.

3) Если сравниваемый символ оказался равен опорному, то они не меняются, а сравниваемый символ становится отсортированным и обозначается оранжевым.

4) Если сравниваемый символ оказался больше опорного, то они меняются местами, сравниваемый символ становится отсортированным и обозначается синим.

5) Последующие сортировки проводим от наибольшего крайнего символа массива по тем же правилам.

Сортируем массив:

П	Л	Е	Х	А	Н	О	В	А	А	Н	Н
Н	Л	Е	Х	А	Н	О	В	А	А	Н	П
Н	Л	Е	Х	А	Н	О	В	А	А	Н	П
Н	Л	Е	Х	А	Н	О	В	А	А	Н	П
Н	Л	Е	П	А	Н	О	В	А	А	Н	Х
Н	Л	Е	Н	А	Н	О	В	А	А	П	Х
Н	Л	Е	Н	А	Н	О	В	А	А	П	Х
Н	Л	Е	Н	А	Н	О	В	А	А	П	Х
Н	Л	Е	Н	А	Н	О	В	А	А	П	Х
Н	Л	Е	Н	А	Н	О	В	А	А	П	Х
Н	Л	Е	Н	А	Н	О	В	А	А	П	Х
Н	Л	Е	Н	А	Н	О	В	А	А	П	Х

• 
  Символы ПХ отсортированы по порядку.
  

Продолжаем сортировку оставшихся символов:

Н	Л	Е	Н	А	Н	О	В	А	А
А	Л	Е	Н	А	Н	О	В	А	Н
А	Л	Е	Н	А	Н	О	В	А	Н
А	Л	Е	Н	А	Н	О	В	А	Н
А	Л	Е	Н	А	Н	О	В	А	Н
А	Л	Е	Н	А	Н	О	В	А	Н
А	Л	Е	Н	А	Н	О	В	А	Н
А	Л	Е	Н	А	Н	Н	В	А	О
А	Л	Е	Н	А	Н	А	В	Н	О
А	Л	Е	А	А	В	Н	Н	Н	О