Навигация
Сортировка разделением (Quicksort)
14078
знаков
7
таблиц
6
изображений
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. Исследование проводилось на массивах с большой степенью неупорядоченности. Для массивов, которые уже являются почти отсортированными, наиболее применим метод сортировки вставками.
Приложение
Блок схемы.
Обменная сортировка.
Сортировка выбором.
Сортировка вставкой.
Похожие работы
... эти методы одинаково хорошо применимы к записям, содержащим как ключевые, так и неключевые поля, то это предположение не ограничивает общности. Традиционно методы сортировки делят на внутренние и внешние. Внутренние методы – это такие методы, которые могут применяться с приемлемой производительностью только к тем спискам данных, которые целиком помещаются в основной (оперативной) памяти ...
... , т.к. всего было проведено 2 теста, школьные учебники по курсу «Право и экономика» и доска для записей перед всем классом. 2.2. ПРОЦЕДУРА и методы ИССЛЕДОВАНИЯ Вопрос применения методов нейро-лингвистического программирования при обучении мало изучен, поэтому и подходящей экспериментальной схемы не нашлось. Нам пришлось разработать её самим. Основным критерием при её создании, к сожалению, была ...
... Это сортировка со смещением 1. В каждой из промежуточных стадий сортировки участвуют либо сравнительно короткие массивы, либо уже сравнительно хорошо упорядоченные массивы, поэтому на каждом этапе можно пользоваться методом простых вставок. Метод сортировки Шелла ещё называется с «убывающим смещением», поскольку каждый проход характеризуется смещением h, таким, что сортируются записи, каждая ...
... памяти ЭВМ, то его упорядочение называют внутренним. Если для хранения упорядочиваемых данных используются внешнее запоминающее устройство, то такое упорядочение называют внешним. Критериями оценки методов сортировки являются: С - количество операций сравнения пар ключей, Р - число перестановок элементов , S - резерв памяти. Среднее количество операций сравнения зависит от ...
0 комментариев