Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
30.
Быстрая сортировка
Базовый алгоритм быстрой сортировки был предложен Хоаром (C.A.R. Hoare) в 1960 году. Алгоритм популярен, потому что легко реализуется и эффективен для различных видов входных данных. Алгоритм относится к классу обменных сортировок. У него два основных недостатка:
Работа быстрой сортировки проста для понимания, и можно дать достаточно точную оценку её вычислительной сложности. Тщательно сбалансированная версия быстрой сортировки, по всей вероятности, будет выполняться быстрее любого другого метода сортировки в большинстве случаев. Однако вычислительная сложность работы алгоритма зависит от степени упорядоченности входных данных и варьируется от линейной до квадратичной.
Базовый алгоритм сортировки действует по принципу “разделяй и властвуй”. Он делит массив на две части, а затем сортирует их независимо друг от друга. Суть метода заключается в процессе разбиения массива элементом key на два подмассива таким образом, что выполняются следующие условия:
Полная сортировка достигается путем деления массива на подмассивы с последующим применением к ним этого же метода. Поскольку процесс разбиения всегда помещает, по меньшей мере, один элемент на свою окончательную позицию, по индукции нетрудно получить формальное доказательство того, что этот рекурсивный метод обеспечивает правильную сортировку. В листинге приведен текст рекурсивной реализации базового
алгоритма быстрой сортировки фрагмента массива k, содержащего n элементов типа T, с k(left) по k(right).
Листинг Базовый рекурсивный алгоритм быстрой сортировки
template <typename T>
void QuickSort(T * k, int left, int right) {
if (right <= left) return;
int i = left + 1, p = right;
T temp, x = k[left];
while (1) {
while (i < p && k[i] <= x) ++i;
while (p >= i && k[p] > x) --p;
if (i < p) {
temp = k[i];
k[i++] = k[p];
k[p--] = temp;
}
else break;
}
k[left] = k[p];
k[p] = x;
QuickSort(k, left, p - 1);
QuickSort(k, p + 1, right);
}
Пусть текущий сортируемый подмассив содержит элементы k(left), k(left + 1), …, k(right). Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента выбирается элемент левого конца массива x = k(left) и инициализируются переменные-индексы i = left + 1 и p = right. Далее начинается просмотр c левого конца массива (i увеличивается на единицу), который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий (x) (первое противоречие). Затем начинается просмотр с правого конца подмассива (p уменьшается на единицу) до тех пор, пока не отыщется элемент меньше разделяющего (второе противоречие). После чего значения элементов k(i) и k(p) меняются местами (разрешаются противо-речия) и индексы изменяются (i = i + 1 и p = p – 1). Когда i станет больше p, необходимо поменять местами значения элементов k(p) и k(left). В результате подмассив поделится на две части k(left), k(lef t+ 1), …, k(p – 1) и k(p + 1), k(p + 2), …, k(right), а рекурсивный процесс продолжится для этих подмассивов независимо друг от друга. Условием выхода из рекурсии является равенство единице длины сортируемого подмассива (left равно righ
Вычислительная сложность быстрой сортировки
Несмотря на все ценные качества, базовая программа быстрой сортировки обладает определенным недостатком: она исключительно неэффективна в некоторых случаях. Например, если она применяется для сортировки массива размером n, который уже упорядочен. После первого разбиения массив делится на подмассивы длиной 0 и n – 1. На следующем шаге образуются подмассивы длиной 0 и n – 2 и т.д. Будем полагать, что любой сортируемый подмассив содержит случайно упорядоченные записи с различными ключами. Оценка вычислительной сложности алгоритма в этом случае приведена в следующем утверждении.
Утверждение 1. Максимальная вычислительная сложность алгоритма быстрой сортировки равна O(n^2)
В случае сортировки упорядоченного массива глубина рекурсии характеризуется величиной O(n), что для больших объемов обрабатываемых данных недопустимо. Следует отметить, что имеются сравнительно простые способы существенного снижения вероятности возникновения такой ситуации.
Наиболее благоприятный для быстрой сортировки случай имеет место, когда на каждой стадии разбиения файл делится на две равные части. Это обстоятельство приводит к тому, что количество операций сравнения, выполняемых в процессе
сортировки, удовлетворяет рекуррентному соотношению
Amin(n)-2Amin(n/2)+n
Слагаемое 2Amin(n/2) соответствует затратам на сортировку двух подфайлов, а n – затратам на сравнение элементов на первом шаге. Данное соотношение имеет решение Amin(n)=nlog2(n)
Однако разбиение массива на две равные части происходит далеко не всегда. Но можно показать, что среднее число операций сравнения, производимое в процессе работы алгоритма, также оценивается величиной ) O(nlogn)