Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Быстрая сортировка. · выбрать элемент, называемый опорным.
|
|
Алгоритм:
· выбрать элемент, называемый опорным.
· сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.
· повторить рекурсивно для «меньших» и «больших».
Оценка эффективности:
· Лучший случай. Для этого алгоритма самый лучший случай — если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива, что дает примерно N lg N сравнений. Это дало бы наименьшее время сортировки.
· Среднее. Даёт в среднем O(n log n) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.
· Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.
Примечание: Количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма.
Достоинства:
· Один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения.
· Прост в реализации.
· Требует лишь дополнительной памяти для своей работы. (Не улучшенный рекурсивный алгоритм в худшем случае памяти)
· Хорошо сочетается с механизмами кэширования и виртуальной памяти.
Недостатки:
· Сильно деградирует по скорости (до) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных.
· Неустойчив — если требуется устойчивость, приходится расширять ключ.
Пирамидальная сортировка (Heapsort)
Алгоритм:
· Строим дерево из последовательности, сразу “сортируя” все элементы от большего(корня) к меньшему(листья).
· В итоге получаем новый массив. Выталкиваем самый большой элемент на верх и меняем с самым правым листом и удаляем его.
