Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2021-04-18 | 74 |
5.00
из
|
Заказать работу |
|
|
Оценим время работы функции _mergeSort(). Оно складывается из времени выполнения двух рекурсивных вызовов, слияния и копирования данных из одного массива в другой. Слияние и копирование выполняется за Θ(n), таким образом, имеем рекуррентное соотношение:
Как показано, например, в [9], решением такого рекуррентного соотношения будет T(n)=Θ(n×logn).
Время работы алгоритма оказывается таким же, как и у быстрой или пирамидальной сортировки. Однако, в связи с необходимостью использования дополнительного массива такого же размера, как исходный, данный алгоритм редко используется для сортировки в оперативной памяти, но является одним из основных алгоритмов внешней сортировки.
Быстрая сортировка Хоара
Быстрая сортировка, как и сортировка слиянием, также является реализацией принципа “разделяй и властвуй”. Элементы сортируемого массива переставляются так, чтобы массив условно разделился на две части – левую и правую, причём никакой элемент из левой части не должен превосходить никакого элемента из правой.
5 | 3 | 8 | 5 | 7 | 1 | 4 | 6 | 2 |
2 | 3 | 4 | 1 | 7 | 5 | 8 | 6 | 5 |
|
Рис. 4.10. Основная идея алгоритма быстрой сортировки
После этого процедура сортировки вызывается рекурсивно для левой и правой части, в результате чего массив будет отсортирован.
Для получения такого разбиения можно действовать следующим образом. Пусть дан массив a[p..r]. Элемент x=a[p] выбирается в качестве граничного (опорного). Нам нужно добиться, чтобы для некоторого q выполнялось следующие условия:
· элементы a[p..q] не больше x
· элементы a[q+1..r] не меньше x
· p£q<r
Строгое неравенство в последнем условии говорит о том, что после разбиения обе получившиеся части должны быть не пустыми, иначе алгоритм зациклится.
|
Разбиение производится следующим образом. Двигаясь от конца массива к началу, найдём элемент £ x. Затем, двигаясь от начала к концу, найдём элемент ³ x. Поменяем эти элементы местами. Будем продолжать действовать таким образом, пока не встретимся где-то внутри массива. Пример выполнения разбиения:
Массив и положения индексов | Комментарии |
4 7 4 2 3 5 Ià ßj | Идём навстречу друг другу: сначала - справа нелево, останавливаемся при a[j]£x, затем – слева направо, останавливаемся при a[i]³x |
4 7 4 2 3 5 I j | Меняем местами a[i] и a[j] |
3 7 4 2 4 5 Ià ßj | Снова движемся навстречу друг другу |
3 7 4 2 4 5 i j | Меняем местами a[i] и a[j] |
3 2 4 7 4 5 iàßj | Снова движемся навстречу друг другу |
3 2 4 7 4 5 i j | Поскольку i£j, разбиение завершено |
После разбиения массива рекурсивно выполнятся сортировка получившихся частей a[p..q] и a[q+1..r].
Приведём пример реализации алгоритма. Здесь a – исходный массив, l и r – диапазон в нём, который нужно отсортировать.
void qsort(int a[], int l, int r)
{ if (l>=r) return;
int i=l-1, j=r+1, x = a[l];
for(;;)
{ do {j--;} while (a[j]>x);
do {i++;} while (a[i]<x);
if (i<j)
{ int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
}
else
{ qsort(a,l,j);
qsort(a,j+1,r);
return;
}
}
}
|
|
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!