Ограниченность простых схем сортировки

Время выполнения алгоритмов по рассмотренным выше схемам в среднем и в худшем случае порядка n². Для больших значений n такие схемы алгоритмов менее целесообразны. Критическое значение n определяется в результате серии опытов, и граничит с n = 100. Для небольших значений n рекомендуется применять простой в реализации алгоритм сортировки Шелла, который является обобщением алгоритма «пузырька». Временная сложность равна n^1.5. Для больших n выгоднее использовать алгоритмы с временем выполнения nlogn. Это так называемые быстрые алгоритмы.

Сортировка Шелла

Эту сортировку придумал Дональд Л.Шелл. В ней весь список рассматривается как совокупность перемешанных подсписков. На первом шаге эти подсписки представляют собой просто пары элементов. На втором шаге в каждой группе по четыре элемента. При повторении процесса число элементов в каждом подсписке увеличивается, а число подсписков уменьшается. Сортировка в подсписках на каждом шаге выполняется путем однократного применения сортировки вставками.

Алгоритм сортировки Шелла

ShellSort(list, N)

//list сортируемый список элементов N число элементов в списке

passes = [log_2 N] // целая часть

while (passes >= 1) do

increment = 2^passes-1 // 2 ^passes-1

for start = 1 to increment do

InsertionSort(list, N, start, increment)

end for

passes = passes - 1

end while

end

Переменная increment содержит величину шага между номерами элементов подсписка. (На рисунке шаг принимает значения 8, 4, 2 и 1.) В алгоритме мы начинаем с шага, на 1 меньшего наибольшей степени двойки, меньшей, чем длина списка. Поэтому для списка из 1000 элементов первое значения шага равно 511. Значение шага также равно числу подсписков. Элементы первого подсписка имеют номера 1 и 1 + increment; первым элементов последнего подсписка служит элемент с номером increment.

При последнем исполнении цикла while значение переменной passes будет равно 1, поэтому при последнем вызове функции InsertionSort значение переменной будет равно 1.

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

1, 4, 10, 23, 57, 132, 301, 701.

 

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

Алгоритм с временем выполнения nlogn является самым эффективным методом внутренней сортировки и поэтому называется быстрой сортировкой. Название алгоритму быстрая сортировка quicksort дал его автор Хоар (Xoare C. A. R). В этом алгоритме среди всех значений выбирается некоторое значение υ в качестве опорного, относительно которого переупорядочиваются элементы массива. Желательно выбирать опорный элемент так, чтобы он разбивал множество значений примерно на две равные части. Далее элементы массива переставляются так, чтобы для некоторого индекса j все переставленные элементы A₁, A₂, A₃,.......A_j имели значения ключей, большие или равные υ. Затем процедура быстрой сортировки рекурсивно применяется к множествам элементов A₁, A₂, A₃,.......A_j и A_j, A_j+1, A_j+2,....... A_n для упорядочивания этих множеств по отдельности. Поскольку значения элементов в первом множестве меньше, чем значения элементов во втором множестве, то исходный массив будет отсортирован правильно. При необходимости этот процесс повторяют и для каждого множества до тех пор пока весь исходный массив не будет упорядочен.

 

Пример.

Воспользуемся способом быстрой сортировки над последовательностью чисел: 3, 1,4, 1, 5, 9, 2, 6, 5, 3. На каждом шаге опорное значение выбирается как наибольшее значение из двух самых левых различных элементов – чисел. Сортировка завершается, когда частичные подмножества, на которые разбивается исходный массив в процессе рекурсивных вызовов процедуры, будут содержать одинаковые ключи.

Каждый этап состоит из двух шагов: сначала для каждого частичного подмножества выбирается свое значение υ, затем элементы в этих подмножествах переставляются в соответствии с выбранным значением υ, тем самым опять разбиваются на два подмножества, к которым рекурсивно применяется процедура сортировки.

Процедура быстрой сортировки.

На первом эт апе для некоторого подмножества надо найти опорный элемент.

1. проверить все ли элементы одинаковы, тогда возвращенное значение равно 0.

2. в противном случае она возвращает индекс наибольшего из первых двух различных значений. Этот наибольший ключ становится опорным элементом.

На втором этапе необходимо произвести разделение подмножества

1. Вводятся два курсора l и r, которые будут перемещаться с двух сторон к середине подмножества.

2. Значения элементов сравниваются с опорным значением.

3. Элементы A(l) и A(r) переставляются, если A(l)>=A(ОпорноеЗначение) и A(r) < A(ОпорноеЗначение)

4. Окончанием процесса – нахождение точки разделения подмножества при l > r и возвращаемое значение l.

 

Этапы быстрой сортировки

 

υ = 3
		1|
υ = 2	υ = 5
	1|				3|
	1|		υ = 3	υ = 6
		3|			5|
	υ = 9
	6|

 

QuickSort(i, j) ‘ Быстрая сортировка i,j - границы массива

//Сортируем элементы A(i), A(i+1),......,A(j) внешнего массива А

//k нач. индекс группы элементов, чьи значения >= ОпорноеЗначение

 

Index = indPoint(i, j) ‘ Поиск Индекса опорного значения

If Index <> 0 Then

PointVal = A(Index)

k = razd(i, j, PointVal) ’Разделение на два подмножества

QuickSort(i, k - 1)

QuickSort(k, j)

End If

End Sub

 

indPoint(i, j) ‘ Поиск Индекса опорного значения

eL = A(i)

Index = i

If i = j Then Index = 0

For kL = i + 1 To j

If A(kL) > eL Then

indPoint = kL

Exit indPoint

ElseIf A(kL) < eL Then

indPoint = i

Exit indPoint

Else

Index = 0

End If

Next kL

indPoint = Index

End

 

razd(i, j, PointVal) ’Разделение множества на два подмножества

L = i

R = j

Do до тех пор пока L > R

p = A(L)

A(L) = A(R)

A(R) = p

Do While A(L) < PointVal

L = L + 1

end While

Do While A(R) >= PointVal

R = R - 1

end While

end Do

razd = L

End

 

Процедура будет работать тем быстрее, если опорное значение будет таким, чтобы разбивало рассматриваемое в данный момент подмножество элементов на две примерно равные части. Например, можно с помощью датчика случайных чисел выбирать три элемента из подмножества и средний (по величине) назначить опорным элементом.

Другим способом реализации алгоритма быстрой сортировки можно получить в зависимости от того, как организована работа с малыми подмножествами. В книге [ ] предлагается значение 9 в качестве порогового значения размера подмножества, ниже которого целесообразно применять простые методы сортировки.

Существует еще один способ «ускорения» быстрой сортировки за счет увеличения используемого пространства памяти компьютера. Можно создать дополнительный массив указателей на записи массива А. Все сравнение значений организовано посредством этих указателей. В этом случае нет необходимости в физическом перемещении самих записей, что значительно быстрее, особенно если они состоят из большого количества полей. В конце выполнении процедуры указатели будут отсортированы слева направо, указывая на записи в нужном порядке. Далее просто переставляются записи в нужном порядке. Отрицательными аспектами этого способа является: использования дополнительного объема памяти под массив указателей и медленное выполнение операций сравнения значений элементов, т.к. следуя за указателем нужно найти нужную запись, затем войти в эту запись, а уже потом взять значение ключевого поля.

Сортировка слиянием

Этот способ сортировки также является рекурсивным. Он так же делит список на два подсписка и рекурсивно их сортирует.

В основе этой сортировки лежит замечание, согласно которому слияние двух отсортированных списков выполняется быстро. Сортировка слиянием делит список пополам, чтобы сформировать два подсписка равного размера. Затем подсписки рекурсивно сортируются и сливаются, образуя полностью отсортированный список. Процесс слияния связан с тем, что подсписки объединяются в рабочий массив, результат копируется в исходный список. Как и в случае с быстрой сортировкой, можем ускорить сортировку, останавливая рекурсию, если подсписки достигают некоторого минимального размера, после чего можно использовать более простую схему (выбором).

Пример работы алгоритма на массиве 3 7 8 2 4 6 1 5..

 

MergeSort(list,first,last)

// list - сортируемый массив, его левая граница first, правая граница last

If first<last then

middle=(first+last)/2

mergeSort(list,first, middle); // сортировать левую половину

mergeSort(list, middle+1,last);// сортировать правую половину

mergeList(list, first, middle, middle+1, last); // слить результаты в общий массив

endIf

end

Функция mergeList на месте двух упорядоченных массивов a[first]...a[middle] и a[middle +1]...a[last] создает единый упорядоченный массив a[first]...a[last].