|
 |
Персональные инструменты
Просмотры |
|
Персональные инструменты |
|
||
|
|
Быстрая сортировка — различия между версиямиМатериал из CustisWiki
Версия 11:34, 17 октября 2005Алгоритм быстрой сортировки (QuickSort) является популярным алгоритмом для сортировки, несмотря на то, что в худшем случае (на некоторых входных массивах) использует время , что, например, хуже, чем сложность в наихудшем случае алгоритма Сортировка слиянием. Дело в том, что анализ «в среднем» и опыт реального использования показали его эффективность.
Быстрая сортировка с детерминированным выбором осиКлючевая идея алгоритма заключается в процедуре «partition», которая за линейное время от размера массива, осуществляет такую перестановку элементов, относительно некоторой «оси» — заданного значения, равного одному из значений сортируемого интервала массива, что переставленный массив состоит из трех интервалов, идущих по порядку:
Первый и последний из упомянутых интервалов могут быть неупорядоченными, поэтому далее, они рекурсивно сортируются процедурой «quicksort_interval». Реализация на Python (и пример работы) алгоритма «Быстрая сортировка с детерминированным выбором оси»: def quicksort(A): def swap(i,j): # Перестановка i-го и j-го элементов массива A temp = A[i]; A[i] = A[j]; A[j] = temp #Перестановка элементов в интервале [left:right) массива А, # таким образом, что, возникают три интервала: # в первой части массива все элементы < осевого значения pivotValue # а во второй = осевому значению. # а во третьей > осевого значения. def partition(left, right, pivotValue): print funcname() ,A[left:right], pivotValue, indexLow = i = left # Нижний и текущий индексы indexHigh = right-1 # Верхний индекс while i <= indexHigh: # Пока есть область не просмотренных элементов. if A[i] < pivotValue: # Если элемент меньше оси swap(i,indexLow) # гоним его в начало интервала indexLow = indexLow + 1 # сужаем область слева i = i + 1 elif A[i] > pivotValue: # Если элемент больше оси swap(i,indexHigh) # гоним его в конец интервала indexHigh = indexHigh - 1 # сужаем область справа else: # A[i]=pivotValue i = i + 1 # сужаем область слева print "->", A[left:indexLow],A[indexLow:indexHigh+1],A[indexHigh+1:right] return (indexLow,indexHigh) def quicksort_interval(left, right): if right > left+1: # Если в интервале [left:right) хотя бы два элемента print funcname(), A[left:right] (indexLow,indexHigh) = partition(left, right, A[left]) quicksort_interval(left, indexLow) quicksort_interval(indexHigh+1, right) quicksort_interval(0, len(A)) return A Sorting: [3, 1, 4, 1, 5, 9, 2, 6, 3, 5, 8, 7]
quicksort_interval: [3, 1, 4, 1, 5, 9, 2, 6, 3, 5, 8, 7]
partition: [3, 1, 4, 1, 5, 9, 2, 6, 3, 5, 8, 7] 3 -> [1, 1, 2] [3, 3] [9, 6, 5, 5, 8, 7, 4]
quicksort_interval: [1, 1, 2]
partition: [1, 1, 2] 1 -> [] [1, 1] [2]
quicksort_interval: [9, 6, 5, 5, 8, 7, 4]
partition: [9, 6, 5, 5, 8, 7, 4] 9 -> [6, 5, 5, 8, 7, 4] [9] []
quicksort_interval: [6, 5, 5, 8, 7, 4]
partition: [6, 5, 5, 8, 7, 4] 6 -> [5, 5, 4] [6] [7, 8]
quicksort_interval: [5, 5, 4]
partition: [5, 5, 4] 5 -> [4] [5, 5] []
quicksort_interval: [7, 8]
partition: [7, 8] 7 -> [] [7] [8]
Sorted: [1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 9]
В представленном выше алгоритме «осью» назначается первый элемент в разбиваемом интервале. Для некоторых последовательностей, это может приводить к неоптимальному поведению, когда при разбиении, один из крайних интервалов сильно меньше другого, или вовсе пустой. Например, такой «плохой» входной последовательностью будет следующая: Sorting: [1, 6, 2, 5, 3, 7, 4]
quicksort_interval: [1, 6, 2, 5, 3, 7, 4]
partition: [1, 6, 2, 5, 3, 7, 4] 1 -> [] [1] [2, 5, 3, 7, 4, 6]
quicksort_interval: [2, 5, 3, 7, 4, 6]
partition: [2, 5, 3, 7, 4, 6] 2 -> [] [2] [3, 7, 4, 6, 5]
quicksort_interval: [3, 7, 4, 6, 5]
partition: [3, 7, 4, 6, 5] 3 -> [] [3] [4, 6, 5, 7]
quicksort_interval: [4, 6, 5, 7]
partition: [4, 6, 5, 7] 4 -> [] [4] [5, 7, 6]
quicksort_interval: [5, 7, 6]
partition: [5, 7, 6] 5 -> [] [5] [6, 7]
quicksort_interval: [6, 7]
partition: [6, 7] 6 -> [] [6] [7]
Sorted: [1, 2, 3, 4, 5, 6, 7]
Видно, что на каждой рекурсии, сортируемый интервал уменьшается только на один осевой элемент. Таким образом, алгоритм на «плохих» входных данных выполняет рекурсий, а общее количество операций (с учетом операций в процедуре «partition» ) будет . Осталось выяснить, часто ли встречаются наихудшие случаи на множестве входных данных. Допустим, входные данные случайны, и их распределение таково, что в каждом интервале длины N попадаемом в процедуру «partition», первый элемент с равной вероятностью может быть k-тым (1 <= k <= N), по величине, "разбивая", тем самым входной интервал на интервалы длины k-1 и N-k-1. Тогда можно записать следующую рекурсивную оценку матожидания сложности алгоритма: Анализ показывает, что при этом предположении (достаточно равномерном распределении входных данных), справедливо матожидание времени работы, асимптотически оптимальное минимальной сложности сортировки:
Быстрая сортировка с вероятностным выбором осиК сожалению, допущенное в предыдущем разделе предположение о равномерности распределения «осей» относительно интервалов, может не встречаться на практике. Например, есть вариации детерминированного алгоритма, для которых «плохими» будут уже отсортированные (или почти отсортированные) последовательности, а таковые часто встречаются в реальных задачах. В таких случаях, когда нельзя «сделать случайными» входные данные, можно внести «элемент случайности» непосредственно в сам алгоритм. В частности, чтобы сохранилась оптимальная оценка матожидания, достаточно сделать вероятностным выбор осевого элемента из разделяемого интервала. Вероятностный алгоритм отличается от детерминированного, только строчкой, где задается выбор вероятностный выбор осевого элемента, однако, как мы увидели, это дает ему возможность «избегать потерь» на входных данных, которые были «наихудшими» для детерминированного алгоритма, и достигнуть оценки матожидания времени работы O(N log N), вне зависимости от входных данных. Реализация на Python (и пример работы) алгоритма «Быстрая сортировка с вероятностным выбором оси»: def quicksort(A): def swap(i,j): # Перестановка i-го и j-го элементов массива A temp = A[i]; A[i] = A[j]; A[j] = temp #Перестановка элементов в интервале [left:right) массива А, # таким образом, что, возникают три интервала: # в первой части массива все элементы < осевого значения pivotValue # а во второй = осевому значению. # а во третьей > осевого значения. def partition(left, right, pivotValue): print funcname() ,A[left:right], pivotValue, indexLow = i = left # Нижний и текущий индексы indexHigh = right-1 # Верхний индекс while i <= indexHigh: # Пока есть область не просмотренных элементов. if A[i] < pivotValue: # Если элемент меньше оси swap(i,indexLow) # гоним его в начало интервала indexLow = indexLow + 1 # сужаем область слева i = i + 1 elif A[i] > pivotValue: # Если элемент больше оси swap(i,indexHigh) # гоним его в конец интервала indexHigh = indexHigh - 1 # сужаем область справа else: # A[i]=pivotValue i = i + 1 # сужаем область слева print "->", A[left:indexLow],A[indexLow:indexHigh+1],A[indexHigh+1:right] return (indexLow,indexHigh) def quicksort_interval(left, right): if right > left+1: # Если в интервале [left:right) хотя бы два элемента print funcname(), A[left:right] (indexLow,indexHigh) = partition(left, right, A[RandomSource.randrange(left, right)]) quicksort_interval(left, indexLow) quicksort_interval(indexHigh+1, right) RandomSource = random.Random(6666) # Инициализируем генератор случайных чисел. quicksort_interval(0, len(A)) return A Sorting: [1, 6, 2, 5, 3, 7, 4]
quicksort_interval: [1, 6, 2, 5, 3, 7, 4]
partition: [1, 6, 2, 5, 3, 7, 4] 6 -> [1, 2, 5, 3, 4] [6] [7]
quicksort_interval: [1, 2, 5, 3, 4]
partition: [1, 2, 5, 3, 4] 2 -> [1] [2] [3, 4, 5]
quicksort_interval: [3, 4, 5]
partition: [3, 4, 5] 4 -> [3] [4] [5]
Sorted: [1, 2, 3, 4, 5, 6, 7]
Реализация на pl/sqlMikle Zaborov 12:34, 17 Oct 2005 (MSD) _public_procedure({quick_sort},{ _param({at_arr}, {IN OUT NOCOPY pk_cmn.TNumberArray},, {массив чисел}) },{Отсортировать массив быстрой сортировкой}, { AS PROCEDURE swap(i INTEGER,j INTEGER) AS l INTEGER; BEGIN l:=at_arr(i); at_arr(i):=at_arr(j); at_arr(j):=l; END; PROCEDURE QuickSort(a_Lo INTEGER,a_Hi INTEGER) AS Lo INTEGER; Hi INTEGER; Mid INTEGER; BEGIN Lo := a_Lo; Hi := a_Hi; Mid := at_arr(TRUNC((Lo + Hi)/2)); LOOP WHILE at_arr(Lo) < Mid LOOP Lo:=Lo+1; END LOOP; WHILE at_arr(Hi) > Mid LOOP Hi:=Hi-1; END LOOP; IF Lo <= Hi THEN Swap(Lo, Hi); Lo:=Lo+1; Hi:=Hi-1; END IF; EXIT WHEN Lo > Hi; END LOOP; IF Hi > a_Lo THEN QuickSort(a_Lo, Hi); END IF; IF Lo < a_Hi THEN QuickSort(Lo, a_Hi); END IF; END; BEGIN QuickSort(at_arr.first,at_arr.last); END; },{})
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». Репликация: База Знаний «Заказных Информ Систем» → «Быстрая сортировка» |
 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
