Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Топ:
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Дисциплины:
2021-04-18 | 76 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!