Данный алгоритм является усовершенствованием алгоритма простого обмена и был предложен К. Хоором.
“Быстрая сортировка” основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов, которые заметно отличаются друг от по номерам.
Пусть в исходной последовательности {xi} выбран некоторый элемент xk = s. Для выполнения сортировки последовательность просматривается в направлении слева направо, пока не будет найден элемент xi>s, а затем просмотр выполняется справа налево, пока не будет найден элемент xj
Затем найденные элементы меняются местами и процесс “просмотра с обменом” продолжается, пока два просмотра не встретятся примерно в середине последовательности. В результате последовательность разделится на две части: левую – со значениями меньшими s, и правую – со значениями большими s. Например, если в последовательности {44, 55, 12, 42, 94, 06, 18, 67} в качестве s выбрать средний элемент, равный 42, то для разделения последовательности потребуются два обмена: 18↔44, 06↔55. Далее аналогичным образом разделяются полученные части последовательности, затем части частей и т. д., пока каждая часть не будет содержать только один элемент. В каждой новой части рекурсивно может быть выполнен аналогичный алгоритм сравнений и обменов, либо использован метод простых вставок или метод сортировки посредством выбора. В частности, при длине каждой части n≤10, как показывают эксперименты, целесообразно использовать метод простых вставок.
Анализ алгоритма быстрой сортировки показывает, что при выборе границы разделения последовательности k из условия k = [n/2] среднее число сравнений составит
C = nlog(n)
а число пересылок
M = (n/6)log(n).
Опубликовал Kest
December 24 2009 19:58:55 ·
1 Комментариев ·
8152 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Oleg27 October 25 2023 15:28:15
кто уже воспользовался бонусами от бк Винлайн ? 1хбеТ рабочее зеркало
Все бонусы БК Винлайн. Фрибет 1000 р за регистрацию без промокода!
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
