Данный алгоритм является усовершенствованием алгоритма простого обмена и был предложен К. Хоором.
“Быстрая сортировка” основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов, которые заметно отличаются друг от по номерам.
Пусть в исходной последовательности {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] среднее число сравнений составит
Главная
Каталог файлов
