Методы внутренней сортировки Обменная сортировка Сравнение с другими методами сортировки (стр. 2 из 2)

5. Сортировка разделением (Quicksort)

Метод сортировки разделением был предложен Чарльзом Хоаром (он любит называть себя Тони) в 1962 г. Этот метод является развитием метода простого обмена и настолько эффективен, что его стали называть "методом быстрой сортировки - Quicksort".

Основная идея алгоритма состоит в том, что случайным образом выбирается некоторый элемент массива x, после чего массив просматривается слева, пока не встретится элемент a[i] такой, что a[i] > x, а затем массив просматривается справа, пока не встретится элемент a[j] такой, что a[j] < x. Эти два элемента меняются местами, и процесс просмотра, сравнения и обмена продолжается, пока мы не дойдем до элемента x. В результате массив окажется разбитым на две части - левую, в которой значения ключей будут меньше x, и правую со значениями ключей, большими x. Далее процесс рекурсивно продолжается для левой и правой частей массива до тех пор, пока каждая часть не будет содержать в точности один элемент. Понятно, что как обычно, рекурсию можно заменить итерациями, если запоминать соответствующие индексы массива. Проследим этот процесс на примере нашего стандартного массива (таблица 2.6).

Таблица 6. Пример быстрой сортировки

Начальное состояние массива	8 23 5 65 |44| 33 1 6
Шаг 1 (в качестве x выбирается a[5])	|--------|8 23 5 6 44 33 1 65|---|8 23 5 6 1 33 44 65
Шаг 2 (в подмассиве a[1], a[5] в качестве x выбирается a[3])	8 23 |5| 6 1 33 44 65|--------|1 23 5 6 8 33 44 65|--|1 5 23 6 8 33 44 65
Шаг 3 (в подмассиве a[3], a[5] в качестве x выбирается a[4])	1 5 23 |6| 8 33 44 65|----|1 5 8 6 23 33 44 65
Шаг 4 (в подмассиве a[3], a[4] выбирается a[4])	1 5 8 |6| 23 33 44 65|--|1 5 6 8 23 33 44 65

Алгоритм недаром называется быстрой сортировкой, поскольку для него оценкой числа сравнений и обменов является O(n?log n). На самом деле, в большинстве утилит, выполняющих сортировку массивов, используется именно этот алгоритм.

6. Сравнение методов

Для сравнения методов сортировки была написана программа, позволяющая выполнить сортировку пятью способами, по возрастанию или убыванию. Заполнение массива производится случайными данными.

Рис 1. Интерфейс программы.

После выполнения сортировки программа выводит количество сравнений и перестановок. При сравнении заполнялась таблица зависимости числа перестановок и числа сравнений от размера массива.

Таблица 7

Метод	Сравнений					Перестановок
Кол-во	16	32	64	128	256	16	32	64	128	256
Пузырёк	135	527	2079	8255	32895	69	201	1150	3644	14648
QuickSort	70	223	486	1228	2771	20	70	160	399	887
Выбором	120	496	2016	8128	32640	11	29	58	124	249
Шелла	73	186	484	1348	3771	19	54	200	756	2537
Вставками	74	315	1177	4819	17525	46	257	1056	4566	17018

На основании данных таблицы были построены графики.

Рис 2. Зависимость числа перестановок от размера массива

Рис 3. Зависимость числа сравнений от размера массива.

Выводы

По результатам замеров производительности методов можно сделать следующие выводы:

1. Наиболее универсальным методом, является метод быстрой сортировки («QuickSort»), он показывает стабильно высокие результаты на любых размерах массивов. На втором месте находится метод Шелла. Его использование может быть обосновано большее простым алгоритмом с точки зрения программиста.

2. Метод вставки эффективен, при условии большого времени выполнения операций перестановки, так как он является абсолютным лидером по количеству перестановок, проигрывая при этом по количеству сравнений.

3. При использовании небольших массивов данных нет большой разницы по скорости между методами сортировки, поэтому целесообразнее применять метод Пузырька или метод вставок.

4. Исследование проводилось на массивах с большой степенью неупорядоченности. Для массивов, которые уже являются почти отсортированными, наиболее применим метод сортировки вставками.

Приложение

Блок схемы.

Обменная сортировка.

Сортировка выбором.

Сортировка вставкой.