Быстрая сортировка(Хоара).

На каждом шаге алгоритма сначала выбирается «средний» элемент, затем переставляются элементы массива так, что массив разделился на две части. Первая часть содержит элементы меньше «среднего» и, возможно, равные ему. Вторая часть содержит элементы больше «среднего» и, возможно, равные ему. После такого деления массива остается только отсортировать его части по отдельности, с которыми поступаем аналогично (делим на две части). И так до тех пор, пока эти части не окажутся состоящими из одного элемента, а массив из одного элемента всегда отсортирован (рисунок 2). В случае, когда массив содержит только одинаковые элементы, выбор «среднего» элемента не производится и сортировка не осуществляется.

Рисунок 2. Быстрая сортировка.

Листинг алгоритма:

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

1. Сортировка.

2. Сортировка простым извлечением.

3. Сортировка Хоара.

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

1. Ознакомиться с теоретической часть лабораторной работы;

2. Выполнить задания в соответствии с вариантом (вариант берётся по номеру журнале);

3. Показать результаты работающей программы преподавателю;

4. На отчёт предоставить:

· Титульный лист;

· Листинг программы с комментариями согласно номеру варианта;

· Блок схема программы;

· Описание программы.

5. Ответить на контрольные вопросы.