Принцип работы быстрой сортировки

Быстрая сортировка

Эффективность алгоритма сортировки прямого обмена

Максимальное число сравнений c_max=n(n-1)/2, а их порядок о(n²). Тогда число перемещений м_max=3c_max=3n(n-1)/2 с порядком о(n²). Если массив уже отсортирован и применяется алгоритм с флажком, то за один проход получаем минимальное число сравнений c_min =n-1, порядок о(n), а перемещения вообще отсутствуют.

Сравнительный анализ прямых сортировок показывает, что обменная сортировка в классическом виде представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора. Если же в нее внесены приведенные выше усовершенствования, то для достаточно упорядоченных массивов пузырьковая сортировка даже имеет преимущество.

Улучшенные методы сортировки. Быстрая сортировка. Её эффективность.

Простые сортировки имеют сложность порядка n², а алгоритмы улучшенных сортировок обладают общей сложностью примерно n*logn.

Если сортируются данные небольшого объёма, то эффективность улучшенных сортировок не заметна. Выгода от улучшенных сортировок становится ощутима во время сортировки данных больших объёмов. Поэтому, если необходимо отсортировать данные объёмом большим чем 100 элементов, то лучше взять один из алгоритмов улучшенной сортировки.

Алгоритм сортировки к. Хоара использует несколько иной механизм выбора значений для обменов, чем обычный алгоритм «пузырька», и называется сортировкой с разделением или быстрой сортировкой. В отличие от «пузырька», в быстрой сортировке производят обмены элементов на больших расстояниях для достижения наибольшей эффективности. Поэтому быстрая сортировка – это улучшенный метод, основанный на обмене.

Самый простой случай для быстрой сортировки – когда n элементов массива расположены в обратном порядке. Данные можно отсортировать, выполнив всего n/2 обменов, если сначала поменять местами самый левый и самый правый элементы и так далее, постепенно продвигаясь с двух сторон к середине.

Данные сортируем по возрастанию. Сначала среди данных выбирается элемент x, относительно которого будут производиться следующие действия. Просматриваем данные, двигаясь слева направо, пока не найдем элемент a[i]>x. Затем просмотрим массив справа налево, пока не найдем элемент a[j]<x. Далее меняются местами эти два элемента a[i] и a[j]. Этот процесс «просмотра с обменом» продолжается до тех пор, пока два просмотра не встретятся где-то в середине массива. После такого просмотра массив разделится на две части. Первая часть – это левая с элементами меньшими или равными x. А вторая часть – правая с элементами большими или равными x. Далее указанный выше процесс повторяется, но уже с первой частью данных, а потом и со второй. Этот процесс дробления частей с обменом элементами однотипен и применяется до тех пор, пока данные не будут отсортированы. Из-за этого применяется рекурсия.

Существуют разные способы выбора элемента x. Это может быть центральный элемент выбранной последовательности или её первый элемент. Можно провести исследование для определения наиболее эффективного место положения выбираемого x.