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