Функция QuickSort сводит сортировку данного ей массива к разделению (partitioning) этого массива на две группы элементов и сортировке этих двух групп по отдельности.
Пример рекурсивного алгоритма с детерменированным(определённым) выбором оси:
Пусть нам нужно отсортировать участок массива A с p-го по q-й элемент включительно, будем называть этот участок подмассивом и обозначать как A[p..q].
- ШАГ 1: Возьмем элемент A[p] за ось и "раскидаем" остальные элементы A[(p+1)..q] по разные стороны от него стороны — меньшие влево, большие --- вправо, то есть переставим элементы подмассива A[p..q] так, чтобы вначале шли элементы меньше либо равные A[p] потом элементы, больше либо равные A[p]. Назовет этот шаг разделением (partition).
- ШАГ 2: Пусть r есть новый индекс элемента A[p]. Тогда, если q - p > 2, вызовем функцию сортировки для подмассивов A[p..(r-1)] и A[(r+1)..q].
Ключевая идея алгоритма заключается в процедуре «partition», которая за линейное время от размера массива, осуществляет такую перестановку элементов, относительно некоторой «оси» — заданного значения, равного одному из значений сортируемого интервала массива, что переставленный массив состоит из трех интервалов, идущих по порядку:
- Элементы меньшие «оси»
- Элементы равные «оси»
- Элементы большие «оси»
Первый и последний из упомянутых интервалов могут быть неупорядоченными, поэтому далее, они рекурсивно сортируются.
Эффективность алгоритма существенно зависит от выбора «оси». Например, если назначать «осью» значение, которое больше или меньше всех элементов, то алгоритм вовсе не будет работать — разбиение никак не будет уменьшать сортируемый интервал и алгоритм зациклится.
Существует много
различных вариантов данного алгоритма,
отличающихся друг от друга сильно и не
очень, в основном функцией партиционирования.
Я же предлагаю Вам не сложный и при этом,
достаточно оптимальный алгоритм.
Прочитал я его в книге «Песни о Паскале»
http://oleg-derevenets.narod.ru/
Он уже модифицирован и улучшен тем, что
оcь выбирается усредненная по 3-м точкам выборки (приближенная
к медиане). Данная модификация алгоритма предусматривает наличие двух указателей в списке. Первый идет снизу, второй - сверху. В основном цикле алгоритма нижний указатель увеличивается до тех пор, пока не будет обнаружен элемент, больший осевого, а верхний уменьшается пока не будет обнаружен элемент, соответственно, меньший. Затем найденные элементы меняются
местами. Этот процесс повторяется пока два указателя не перекроются. Эти внутренние циклы работают очень быстро, поскольку исключаются накладные расходы на проверку конца списка.
местами. Этот процесс повторяется пока два указателя не перекроются. Эти внутренние циклы работают очень быстро, поскольку исключаются накладные расходы на проверку конца списка.
def QuickPas(s, aL, aR):
l, r=aL, aR
mid = (s[l]+s[(l+r)/2]+s[r])/3
while lmid:r-=1
if l<=r:
if s[l]>s[r]:
s[l], s[r] = s[r], s[l]
l+=1
r-=1
if r>aL: QuickPas(s, aL, r)
if l<aR: QuickPas(s, l, aR)
Математический подход
Не строгая оценка
Рассмотрим наихудший случай. Допустим, что нам не везет и в качестве опорного элемента выбирается либо мин. либо макс. элемент. Тогда на след рекурсивном вызове у нас останется ровно n-1 элементов. Следовательно высота нашего дерева будет n-1 и время O(n).
В наилучшем же случае, мы будем делить массив ровно пополам и получим идеально сбалансированное бинарное дерево, т.е. O(log(n)).
Итак, на весах лучший и наихудший случаи, каков же средний?
Вероятность выбора наудачу точно средний элемент довольно низка, а именно равна 1/n. Но допустим, что разделитель является достаточно хорошим, если он находится в центральной части массива, т.е. в диапазоне от n/4 до 3n/4. Таких элементов уже больше и вероятность выбора одного из них равна 1/2.
Оценим наихудший случай теперь. При выборе плохого элемента из достаточно хороших, большая часть массива содержит 3n/4 элементов. Самая длинная ветвь такого дерева проходит через части размером n, 3n/4, (3/4)2n...и т.д. до 1 элемента. Длина этой ветви = высоте дерева
Но только половина выбираемых произвольно разделителей являются достаточно хорошими, а другие плохими. Т.к. вероятность выбора того или иного равна 1/2, то и высота дерева может увеличиться самоее большее в 2 раза
Более подробный анализ показывает, что после n вставок средняя высота дерева составляет приблизительно 2ln(n), что приблизительно равно 1.3861log(n), т.е. всего на 39% больше чем идеально сбалансированное бинарное дерево.
Строгая оценка
Наихудший и наилучший случаи не требуют строгого доказательства и полностью совпадают с рассмотрением выше. Здесь же рассмотрим средний случай.
Для анализа среднего случая рассмотрим каждую из этих возможностей и усредним результаты. При анализе наихудшего случая мы заметили, что процедура разбиения делает N — 1 сравнений, разбивая список из N элементов. Слияние этих списков не требует никаких действий. Наконец, заметим, что когда она возвращает значение оси(P), происходит рекурсивный вызов процедуры Quicksort на списках длины Р — I и N — Р. Проводимый нами анализ среднего случая должен учитывать все N возможных значений .
Если повнимательней посмотреть на сумму, то видно, что аргумент первого слагаемого пробегает значения от 0 до N — 1, а аргумент второго слагаемого — те же значения, но в порядке убывания.
Это означает, что каждое из слагаемых А(г) участвует в сумме дважды, и формулу можно упростить:
теперь давайте посмотрим сразу на 2 формулы для A(N) и для A(N — 1).
Эти два выражения отличаются лишь несколькими членами.
Чтобы избавиться от дробей, подсчитаем A(N)-N и A(N—1)-(N—1).
Путем не сложных преобразований получим окончательное рекуррентное соотношение
Его детальный анализ дает A(N) = 1.4(N +1)log2N. Таким образом, средняя
сложность алгоритма быстрой сортировки равна O(Nlog2N).
Улучшаем алгоритм
Вся сложность алгоритма Хоара заключается в процедуре разделения массива на 2 половины, что зависит от правильного выбора оси разбиения и чем она ближе к медиане, тем лучше. Следовательно, если мы найдём метод приблизиться к ней(медиане) тем все станет красочнее и пушистее.
Методы основные следующие:
- алгоритм выбора значения наиболее приближенного к медиане
- вероятностный выбор оси
Описанный выше алгоритм относится, как раз к 1 пункту. Там мы находим элемент по 3-м точкам и в среднем он оказывается ближе к медиане, чем постоянный выбор оси.
2 пункт реализовать так же не сложно, что описывается в "инженерном подходе". Можно отметить, что данная модификация является не столь эффективной как 1-я, однако спасает нас от деградации алгоритма при граничных случаях (т.е. сводит почти к 0 вероятность выполнения алгоритма за квадратичное время).
Инженерный подход
Рассмотрим простенький вариантик с использованием встроенной в Питон возможностью условной генерации списков вместо использования функции partition.
def qsort1(list):
if list == []:
return []
else:
pivot = list[0]
lesser = qsort1([x for x in list[1:] if x < pivot])
greater = qsort1([x for x in list[1:] if x >= pivot])
return lesser + [pivot] + greater
И его однострочная версия
def qsortr2(list):
return [] if list==[] else qsortr2([x for x in list[1:] if x < list[0]]) + [list[0]] + qsortr2([x for x in list[1:] if x >= list[0]])
На данных примерах показывается лаконичность и изящность языка, надеюсь вы оценили :)
На сладкое, привожу вам вариант, которому меня научил в университете великий Деон!) Версия избавлена от рекурсии, классическим способом - введением стека, в котором хранятся границы наших интервалов.
def QuickSort(a):
w = [x for x in xrange(4 + len(a) / 2)]#создаём стек
k = 0#дно
w[0] = 0#указатель на позицию левой границы половины
w[1] = len(a) - 1#-||- правой
while (k >= 0):
i = QuickSortPos(a, w[k], w[k + 1])
if(i != w[k + 1]):RL =i + 1#левая граница правого подъинтервала
else:RL =w[k + 1]
RR = w[k + 1]#Правая граница правого подъинтервала
LL = w[k]#Левая граница левого подъинтервал
if(i != w[k]):LR =i - 1#Правая граница левого подъинтервал
else:LR =w[k]
k -= 2#удалить текущий интервал
if (RL != RR):k += 2; w[k] = RL; w[k + 1] = RR
if (LL != LR):k += 2; w[k] = LL; w[k + 1] = LR
return
def QuickSortPos(a, left, right):
i = left
j = right - 1
while (True):#чтобы поставить разделяющий элемент на свое место
while (a[i] < a[right]): i+=1
while (a[j] > a[right] and j > left): j-=1
if (i >= j): break
a[i],a[j] = a[j],a[i]
a[right],a[i] = a[i],a[right]
return i
Сразу скажу, что он показывает максимальную производительность из все виденных мной.Стоит сказать пару слов про использование методов оптимизации и их применимости на практике.
Быстрая сортировка с вероятностным выбором оси
К сожалению, предположение о равномерности распределения «осей» относительно интервалов, может не встречаться на практике. Например, есть вариации детерминированного алгоритма, для которых «плохими» будут уже отсортированные (или почти отсортированные) последовательности, а таковые часто встречаются в реальных задачах. В таких случаях, когда нельзя «сделать случайными» входные данные, можно внести «элемент случайности» непосредственно в сам алгоритм. В частности, чтобы сохранилась оптимальная оценка математического ожидания, достаточно сделать вероятностным выбор осевого элемента из разделяемого интервала.
Вероятностный алгоритм отличается от детерминированного, только строчкой, где задается выбор вероятностный выбор осевого элемента, для первого алгоритма она будет выглядеть следующим образом(indexLow,indexHigh)=partition(left,right,A[RandomSource.randrange(left, right)])
где RandomSource создаётся перед quicksort_interval(0, len(A)) так
RandomSource = random.Random(6666) # Инициализируем генератор случайных чисел.
К сожалению, реализация Random сама по себе привносит большие
задержки. Я так и не нашел входных данных, при которых он выиграл у первого варианта.
В большинстве зарубежных книжных изданиях, представлен данный алгоритм:
def partition(A, left, right):
# indexLow = left+1 # Нижний и текущий индексы
# indexHigh = right-1
pivotPoint=left # Верхний индекс
pivotVal = A[left]
i=left+1
while i <= right:# Пока есть область не просмотренных элементов.
if A[i] < pivotVal:
pivotPoint+=1# Если элемент меньше оси
if i>pivotPoint:#мое улучшение :) убирает перестановки эл-та с самим собой
A[i], A[pivotPoint]=A[pivotPoint],A[i]# гоним его в начало интервала
# indexLow = indexLow + 1 # сужаем область слева
i +=1
# print A, left, pivotPoint
A[left], A[pivotPoint] = A[pivotPoint], A[left]
return pivotPoint
В основном, методы
призванные приблизить выполнение
алгоритма к оптимальному, за счет поиска
более точного положения оси, лишь
усложняет логику, что приводит к
увеличению числа сравнений, обменов
или того и другого одновременно. Если Вы
заинтересуетесь данной проблемой, прошу
заметить, что операции сравнения дешевле
обменов, а следовательно стоит уменьшать
кол-во вторых, чаще за счет увеличения
первых.
Экспериментально доказано, что в среднем алгоритм быстрой сортировки работает в 2-3 раза быстрее сортировок слиянием и пирамидальной.
Производительность
Тестирование проводилось на списке из 50000 не повторяющихся элементов.
- первый алгоритм 54074 function calls in 0.572 seconds
- второй алгоритм избавленный от рекурсии 33395 function calls in 0.432 seconds
- третий - однострочная Python версия 100004 function calls (4 primitive calls) in 0.708 seconds
- Встроенная реализация сортировки list.sort() 4 function calls in 0.004 CPU seconds
Используемая литература:
"по разные стороны от него стороны"
ОтветитьУдалитькупить семена адениума
ОтветитьУдалитьЭкзотические растения свежиесемена адениума и другие комнатные цветы.
еще