Быстрая сортировка
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена известного в том числе своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь
производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы.
Общая идея алгоритма состоит в следующем:
Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива (обычно центральный элемент массива). От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность.
Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие».
Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.
В процессе работы программы происходит последовательное создание и заполнение случайными числами 1000 массивов для каждой заданной длины. Далее происходит сортировка данных.
Помимо этого, фиксируется количество операций (перестановок и сравнений) в специально созданные переменные.
Полный код программы представлен в приложении В. Результат работы программы представлен на рисунке 2.3.1.
Рисунок 2.3.1 - Результат работы программы 3
В консольном выводе представляется размерность каждой тысячи массивов, среднее значение от суммы операций, а также среднее время выполнения сортировки.
Таблица 5 представляет собой таблицу со значениями длины массивов и средними значениями количества операций.
Таблица 5 - Средние значения количества операций быстрой сортировки
Размерность массивов |
Среднее количество операций |
1 |
1,000 |
2 |
8,505 |
3 |
14,766 |
4 |
25,364 |
5 |
35,650 |
10 |
93,955 |
15 |
160,247 |
20 |
231,611 |
25 |
305,857 |
30 |
383,750 |
50 |
715,712 |
75 |
1165,937 |
100 |
1637,832 |
250 |
4727,572 |
500 |
10412,342 |
Далее необходимо построить график зависимости количества операций от длины массивов. График представлен на рисунке 2.3.2.
Рисунок 2.3.2 - График зависимости количества операций от длины массивов
Таблица 6 представляет собой таблицу со значениями длины массивов и среднего времени выполнения сортировки (среднего времени выполнения всех сравнений и перестановок).
Таблица 6 - Значения среднего времени выполнения операций быстрой сортировки
Размерность массивов |
Затраченное время (с) |
1 |
0,000000 |
2 |
0,000000 |
3 |
0,000000 |
4 |
0,000000 |
5 |
0,000000 |
10 |
0,000001 |
15 |
0,000001 |
20 |
0,000001 |
25 |
0,000002 |
30 |
0,000002 |
50 |
0,000004 |
75 |
0,000006 |
100 |
0,000008 |
250 |
0,000023 |
500 |
0,000046 |
Далее необходимо построить график зависимости затраченного на выполнение сортировки времени от длины массива. График представлен на рисунке 2.3.3.
Рисунок 2.3.3 - График зависимости затраченного времени от длины массивов
На основе полученных графиков, построим графики зависимостей y=n, y=n*log(n), y=n^2, y=n^3. Графики представлены на рисунке 2.3.4.
Рисунок 2.3.4 – Графики зависимости для быстрой сортировки
Проанализировав полученные результаты, можно сделать вывод о том, что график количества операций лежит между графиками y=n*log(n) и y=n^2. А следовательно, лучшее время для быстрой сортировки O(n*log(n)), а худшее - О(n^2).