Алгоритмы базовых и улучшенных сортировок

Порядковые статистики.

Цель работы: изучение и практическое применение алгоритмов сортировок:

- основных базовых алгоритмов;

- улучшенных эффективных алгоритмов, построенных на основе базовых.

Домашнее задание:

1. Изучить базовые алгоритмы сортировок:

а) с помощью прямого включения и его модификация двоичным включением;

б) сортировка с помощью прямого выбора;

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

2. Освоить эффективные алгоритмы улучшенных методов сортировок:

а) сортировка Шелла (с помощью включений с уменьшением расстояний);

б) сортировка с помощью дерева (пирамидальная HeapSort), базируется на прямом выборе;

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

3. Освоить применение алгоритмов сортировок для вычисления значения i-той порядковой статистики.

Порядок выполнения работы:

1. Открыть проект Delphi Structures.

2. На главной форме в главное меню добавить пункт «Лабораторная работа №3», при выборе которого должно появляться вертикальное подменю из двух пунктов:

1) SortBase

2) SortBest

Часть I (пункты 3÷6)

3. При выборе пункта 1) SortBase должно появляться окно модуля «Sortirovka1», для этого соответствующий модуль с формой необходимо добавить в проект.

4. Установить на форму модуля «Sortirovka1» компоненты, обеспечивающие ввод исходных данных, вывод результатов и управляющую кнопку, в соответствии с вариантом задания из таблицы 3.1.

5. В обработчике события onClick управляющей кнопки запрограммировать на языке Object Pascal алгоритм базовой сортировки в соответствии со своим вариантом задания. Отладить приложение и продемонстрировать работу преподавателю.

6. Составить отчет, в котором помимо текста обработчика, распечатки результатов и блок-схемы алгоритма, должен быть сравнительный анализ вашего варианта с алгоритмами других базовых методов сортировки.

Часть II (пункты 7÷10)

7. При выборе пункта SortBest должно появляться окно модуля «Sortirovka2», для этого в проект необходимо добавить соответствующий модуль с формой.

8. Установить на форму компоненты для ввода исходных данных, управляющую кнопку и для вывода результатов сортировки, в соответствии с вариантом задания из таблицы 3.2.

9. В обработчике события onClick запрограммировать и отладить алгоритм улучшенного метода сортировки в соответствии с вариантом. Продемонстрировать работу приложения преподавателю.

10. Составить отчет в соответствии с п.6, но, для улучшенных методов сортировки. Защитить всю работу преподавателю.

Таблица 3.1

№ вар.	Текст задания
1.	const n=31; var x: array [1..n] of integer; p: integer; k: 1..n; found: boolean; Простыми вставками упорядочить элементы массива х по убыванию. Для числа р проверить: если р входит в массив х, то found присвоить TRUE, а к – номер элемента равного р, и found присвоить FALSE иначе.
2.	var x: array [1..20] of 1..21; y: 1..21; Пусть все элементы массива х различны. Расположить их по возрастанию методом бинарных вставок и, найти y– то единственное целое є [1..21], которого нет в этом массиве.
3.	var x: array [1..20] of real; Упорядочить массив по возрастанию, используя сортировку обменом (метод «пузырька»). Учесть в программе, что если при очередном просмотре не было ни одного обмена (перестановки), то массив уже упорядочен, и процесс необходимо завершить с выводом полученной упорядоченной последовательности.
4.	const n=20; var x: array [1..n] of real; Упорядочить массив х по неубыванию, используя сортировку простыми вставками (сравнение в обратном направлении: от (i -1) до 1) и модифицировать алгоритм для просмотра готового массива (в методе простых вставок) в прямом направлении (от 1-го до (i -1)-го элемента).
5.	var x: array [1..20] of 1..21; y: 1..21; Пусть все элементы массива х различны. Расположить их по убыванию методом прямого выбора и, используя бинарный поиск, найти y – то единственное целое число є [1..21], которого нет в этом массиве.
6.	var x: array [1..20] of real; Упорядочить массив по убыванию, используя сортировку методом «пузырька». Если при очередном просмотре массива не было ни одного обмена, то массив уже упорядочен, и процесс необходимо завершить. Выдать на печать отсортированный массив и число фактически совершенных просмотров массива в ходе сортировки.
7.	var x: array [1..20] of real; Упорядочить массив по возрастанию, используя метод «пузырька» с чередованием направлений последовательных просмотров – метод «шейкерной» сортировки. Проанализировать в сравнении пузырьковую и шейкерную сортировки.
8.	const n=20; var x: array [1..n] of integer; // сортируемый массив Запрограммировать отображение n неповторяющихся ключей (целых) на битовое поле и воспроизведение в исходном массиве или файле отсортированной последовательности ключей – использование отобразительной сортировки. Простейшее битовое поле для отображения: var Mno: set of 0..255; Для широкого диапазона ключей использовать гипермножество – массив множеств: Type MasMno=array of set of 0..22;
9.	Даны натуральные числа а₁,..а_n_. Пусть а₁,..а_n – перестановка чисел 1,.. n. Написать программу для получения натуральных r_1,..,r_n таких, что r_ai=i для i=1,..,n.

Таблица 3.2

№ вар.	Текст задания
1.	var x: array [1..1000] of real; Применив алгоритм сортировки Шелла (сортировка с помощью включений с уменьшающимися расстояниями), отсортировать массив х в порядке неубывания. При выборе расстояний пользоваться следующими рекомендациями (Кнут Д. «Искусство программирования для ЭВМ» т.1): h_k_-1=2*h_k-1 (…9,5,3,1), h_t=1, t=[log₂n] +1
2.	Используя сдвигающий алгоритм построения пирамиды Флойда, для заданного массива целочисленных ключей построить пирамиду, распечатать ключи получившегося бинарного дерева (например, в виде массива, для которого должно выполняться правило: для любого i: j=2i или j=2i+1, h_i≤h_j) и распечатать минимальный элемент массива.
3.	Пусть построена пирамида Флойда: рис. 1 Ввести ключи этой пирамиды в ОП в виде массива, элементы которого подчиняются правилу задания бинарного дерева. Написать процедуру сдвига алгоритма Флойда и, используя ее, отсортировать ключи пирамиды в порядке убывания.
4.	Ввести ключи бинарного дерева (рис. 1) в ОП. Запрограммировать сдвигающий алгоритм Флойда для упорядочения заданного массива ключей в порядке возрастания (пирамидальная сортировка).
5.	Сформировать массив псевдослучайных целых чисел в диапазоне [-100…100]. Количество элементов задавать с клавиатуры. Используя рекурсивный алгоритм сортировки с помощью разделения (сортировка Хоара - QuickSort) упорядочить сформированный массив по неубыванию его элементов. Результат сортировки вывести в объект класса TMemo.
6.	Написать и отладить программу, которая использует итеративный алгоритм сортировки массива по убыванию с помощью разделения, в котором стек для запоминания требований (границы части массива, требующей дальнейшего разделения) необходимо организовать как массив записей с двумя целочисленными полями: var stack: array [1..30] of record Left, Right: integer; end;
7.	Запрограммировать и отладить алгоритм Хоара для нахождения медианы заданного массива целых чисел. Использовать рекурсивный алгоритм сортировки разделением.
8.	Сформировать массив целых псевдослучайных чисел в диапазоне [-20..20]. Отсортировать массив в порядке возрастания, используя алгоритм сортировки последовательностей прямым слиянием (алгоритм Боуза и Нельсона). Структурировать программу, организовав рекурсивную процедуру для слияния списков (частей массива) равного размера.

Контрольные вопросы

1. Определение сортировки, устойчивой сортировки.

2. Цель сортировки.

3. Сформулируйте полное условие окончания процесса сортировки прямым включением. Объясните применение приема «барьера», позволяющего сократить проверяемое условие.

4. Идея алгоритма двоичного включения, как модификация алгоритма прямого включения.

5. Приведите блок- схему алгоритма прямым выбором.

6. Что мы называем «пузырьком» в алгоритме метода сортировки прямым обменом?

7. В чем заключается модификация алгоритма пузырьковой сортировки, основанная на том, что в алгоритме просматривается ассиметрия: пузырьки на «тяжелом» и «легком» концах массива встают на свое место абсолютно по-разному.

8. Объясните на примере идею сортировки Шелла, как сортировки с помощью включений с уменьшающимися расстояниями.

9. Для последовательности ключей

44 55 12 42 94 18 06 67

постройте двоичное дерево выбора и идентифицируйте его корень.

10. Сформулируйте основное правило, с помощью которого можно прочитать пирамиду (двоичное дерево) в линейной последовательности ключей.

11. Объясните процедуру «сдвига элемента» в алгоритме Флойда.

12. Сформулируйте основную идею алгоритма быстрой сортировки Хоара.

13. Дайте определение i-той порядковой статистики, медианы.

14. Определение слияния последовательностей.

15. Основной недостаток методов сортировки слиянием.

Лабораторная работа №4