Как сделать быструю сортировку с. Быстрая сортировка и с чем её едят
Быстрая сортировка и с чем её едят
- Чулан *
Всем привет! Я расскажу об алгоритме быстрой сортировки и покажу, как его можно реализовать программно.
Итак, быстрая сортировка, или, по названию функции в Си, Qsort - это алгоритм сортировки, сложность которого в среднем
составляет O(n log(n)). Суть его предельно проста: выбирается так называемый опорный элемент, и массив делится на 3 подмассива: меньших опорного, равных опорному и больших опорного. Потом этот алгоритм применяется рекурсивно к подмассивам.
Алгоритм
- Выбираем опорный элемент
- Разбиваем массив на 3 части
- Создаём переменные l и r - индексы соответственно начала и конца рассматриваемого подмассива
- Увеличиваем l, пока l-й элемент меньше опорного
- Уменьшаем r, пока r-й элемент больше опорного
- Если l всё ещё меньше r, то меняем l-й и r-й элементы местами, инкрементируем l и декрементируем r
- Если l вдруг становится больше r, то прерываем цикл
- Повторяем рекурсивно, пока не дойдём до массива из 1 элемента
void qsort (int b, int e)
{
int l = b, r = e;
int piv = arr[(l + r) / 2]; // Опорным элементом для примера возьмём средний
while (l <= r)
{
while (arr[l] < piv)
l++;
while (arr[r] > piv)
r--;
if (l <= r)
swap (arr, arr);
}
if (b < r)
qsort (b, r);
if (e > l)
qsort (l, e);
} /* ----- end of function qsort ----- */// qsort (0, n-1);
* This source code was highlighted with Source Code Highlighter .
Эта реализация имеет ряд недостатков, таких как возможное переполнение стека из-за большого количества вложенной рекурсии и то, что опорным элементом всегда берётся средний. Для примера это, может, и нормально, но при решении, например, олимпиадных задач, хитрое жюри может специально подобрать такие тесты, чтобы на них это решение работало слишком долго и не проходило в лимит. В принципе, в качестве опорного элемента можно брать любой, но лучше, чтобы он был максимально приближен к медиане, поэтому можно выбрать его случайно или взять средний по значению из первого, среднего и последнего. Зависимость быстродействия от опорного элемента - один из недостатков алгоритма, ничего с этим не поделать, но сильная деградация производительности происходит редко, обычно если сортируется специально подобранный набор чисел. Если всё-таки нужна сортировка, работающая гарантированно быстро, можно использовать, например, пирамидальную сортировку, всегда работающую строго за O(n log n). Обычно Qsort всё же выигрывает в производительности перед другими сортировками, не требует много дополнительной памяти и достаточно прост в реализации, поэтому пользуется заслуженной популярностью.
Писáл сам, изредка поглядывая на Википедию . Пользуясь случаем, передаю спасибо замечательным преподавателям и студентам ПетрГУ, научившим меня множеству полезных вещей, в том числе и этому алгоритму!
Теги: Qsort, быстрая сортировка, алгоритмы сортировки, алгоритмы, C
Обновлено: 18.03.2019
Быстрая сортировка (quick sort ), или сортировка Хоара - один из самых быстрых алгоритмов сортирования данных.
Алгоритм Хоара - это модифицированный вариант метода прямого обмена. Другие популярные варианты этого метода - сортировка пузырьком и шейкерная сортировка , в отличии от быстрой сортировки, не очень эффективны.
Принцип работы алгоритма быстрой сортировки
Идея алгоритма следующая:
- Необходимо выбрать опорный элемент массива, им может быть любой элемент, от этого не зависит правильность работы алгоритма;
- Разделить массив на три части, в первую должны войти элементы меньше опорного, во вторую - равные опорному и в третью - все элементы больше опорного;
- Рекурсивно выполняются предыдущие шаги, для подмассивов с меньшими и большими значениями, до тех пор, пока в них содержится больше одного элемента.
Поскольку метод быстрой сортировки разделяет массив на части, он относиться к группе алгоритмов разделяй и властвуй .
Реализация быстрой сортировки
using System; class Program { //метод для обмена элементов массива static void Swap(ref int x, ref int y) { var t = x; x = y; y = t; } //метод возвращающий индекс опорного элемента static int Partition(int array, int minIndex, int maxIndex) { var pivot = minIndex - 1; for (var i = minIndex; i < maxIndex; i++) { if (array[i] < array) { pivot++; Swap(ref array, ref array[i]); } } pivot++; Swap(ref array, ref array); return pivot; } //быстрая сортировка static int QuickSort(int array, int minIndex, int maxIndex) { if (minIndex >= maxIndex) { return array; } var pivotIndex = Partition(array, minIndex, maxIndex); QuickSort(array, minIndex, pivotIndex - 1); QuickSort(array, pivotIndex + 1, maxIndex); return array; } static int QuickSort(int array) { return QuickSort(array, 0, array.Length - 1); } static void Main(string args) { Console.Write("N = "); var len = Convert.ToInt32(Console.ReadLine()); var a = new int; for (var i = 0; i < a.Length; ++i) { Console.Write("a[{0}] = ", i); a[i] = Convert.ToInt32(Console.ReadLine()); } Console.WriteLine("Упорядоченный массив: {0}", string.Join(", ", QuickSort(a))); Console.ReadLine(); } }Метод Partition возвращает индекс опорного елемента, который делит массив на элементы меньше опорного слева, и элементы больше опорного справа. В самом методе в качестве опорного выбирается последний элемент, а обход осуществляется от начала массива.
Выбирая алгоритм сортировки для практических целей, программист, вполне вероятно, остановиться на методе, называемом «Быстрая сортировка» (также «qsort» от англ. quick sort). Его разработал в 1960 году английский ученый Чарльз Хоар, занимавшийся тогда в МГУ машинным переводом. Алгоритм, по принципу функционирования, входит в класс обменных сортировок (сортировка перемешиванием, пузырьковая сортировка и др.), выделяясь при этом высокой скоростью работы.
Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному.
Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.
Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:
- разбиение массива относительно опорного элемента;
- рекурсивная сортировка каждой части массива.
Разбиение массива.
Еще раз об опорном элементе. Его выбор не влияет на результат, и поэтому может пасть на произвольный элемент. Тем не менее, как было замечено выше, наибольшая эффективность алгоритма достигается при выборе опорного элемента, делящего последовательность на равные или примерно равные части. Но, как правило, из-за нехватки информации не представляется возможности наверняка определить такой элемент, поэтому зачастую приходиться выбирать опорный элемент случайным образом.
В следующих пяти пунктах описана общая схема разбиения массива (сортировка по возрастанию):
- вводятся указатели first и last для обозначения начального и конечного элементов последовательности, а также опорный элемент mid ;
- вычисляется значение опорного элемента (first +last )/2, и заноситься в переменную mid ;
- указатель first смещается с шагом в 1 элемент к концу массива до тех пор, пока Mas [first ]>mid . А указатель last смещается от конца массива к его началу, пока Mas [last ]<mid ;
- каждые два найденных элемента меняются местами;
- пункты 3 и 4 выполняются до тех пор, пока first
После разбиения последовательности следует проверить условие на необходимость дальнейшего продолжения сортировки его частей. Этот этап будет рассмотрен позже, а сейчас на конкретном примере выполним разбиение массива.
Имеется массив целых чисел Mas , состоящий из 8 элементов (рис. 5.5): Mas . Начальным значением first будет 1, а last – 8. Пройденная часть закрашивается голубым цветом.
В качестве опорного элемента возьмем элемент со значением 5, и индексом 4. Его мы вычислили, используя выражение (first +last )/2, отбросив дробную часть. Теперь mid =5.
Первый элемент левой части сравнивается с mid . Mas >mid , следовательно first остается равным 1. Далее, элементы правой части сравниваются с mid . Проверяется элемент с индексом 8 и значением 8. Mas >mid , следовательно last смещается на одну позицию влево. Mas <mid , следовательно last остается равным 7. На данный момент first =1, а last =7. Первый и седьмой элементы меняются местами. Оба указателя смещаются на одну позицию каждый в своем направлении.
Алгоритм снова переходит к сравнению элементов. Второй элемент сравнивается с опорным: Mas >mid, следовательно first остается равным 2. Далее, элементы правой части сравниваются с mid . Проверяется элемент с индексом 6 и значением 1: Mas <mid , следовательно last не изменяет своей позиции. На данный момент first =2, а last =6. Второй и шестой элементы меняются местами. Оба указателя смещаются на одну позицию каждый в своем направлении.
Алгоритм снова переходит к сравнению элементов. Третий элемент сравнивается с опорным: Mas <mid , следовательно first смещается на одну позицию вправо. Далее, элементы правой части сравниваются с mid . Проверяется элемент с индексом 5 и значением 9: Mas >mid , следовательно last смещается на одну позицию влево. Теперь first =last =4, а значит, условие first <last не выполняется, этап разбиения завершается.
На этом этап разбиения закончен. Массив разделен на две части относительно опорного элемента. Осталось произвести рекурсивное упорядочивание его частей.
Рекурсивное доупорядочивание
Если в какой-то из получившихся в результате разбиения массива частей находиться больше одного элемента, то следует произвести рекурсивное упорядочивание этой части, то есть выполнить над ней операцию разбиения, описанную выше. Для проверки условия «количество элементов > 1», нужно действовать примерно по следующей схеме:
Имеется массив Mas [L ..R ], где L и R – индексы крайних элементов этого массива. По окончанию разбиения, указатели first и last оказались примерно в середине последовательности, тем самым образуя два отрезка: левый от L до last и правый от first до R . Выполнить рекурсивное упорядочивание левой части нужно в том случае, если выполняется условие L <last . Для правой части условие аналогично: first <R .
Реализации алгоритма быстрой сортировки:
Код программы на C++:
#include "stdafx.h"
#include
#include "stdafx.h" #include #include using namespace std ; const int n = 7 ; int first , last ; //функция сортировки void quicksort (int * mas , int first , int last ) int mid , count ; int f = first , l = last ; mid = mas [ (f + l ) / 2 ] ; //вычисление опорного элемента while (mas [ f ] < mid ) f ++ ; while (mas [ l ] > mid ) l -- ; if (f <= l ) //перестановка элементов count = mas [ f ] ; mas [ f ] = mas [ l ] ; mas [ l ] = count ; f ++ ; l -- ; } while (f < l ) ; if (first < l ) quicksort (mas , first , l ) ; if (f < last ) quicksort (mas , f , last ) ; //главная функция void main () setlocale (LC_ALL , "Rus" ) ; int * A = new int [ n ] ; srand (time (NULL ) ) ; cout << "Исходный массив: " ; for (int i = 0 ; i < n ; i ++ ) A [ i ] = rand () % 10 ; cout << A [ i ] << " " ; first = 0 ; last = n - 1 ; quicksort (A , first , last ) ; cout << endl << "Результирующий массив: " ; for (int i = 0 ; i < n ; i ++ ) cout << A [ i ] << " " ; delete A ; system ("pause>>void" ) ; |
Код программы на Pascal:
Delphi/Pascal
program qsort;
uses crt;
const n=7;
var A: array of integer;
first, last, i: integer;
{процедура сортировки}
procedure quicksort(var mas: array of integer; first, last: integer);
var f, l, mid, count: integer;
begin
f:=first;
l:=last;
mid:=mas[(f+l) div 2]; {вычисление опорного элемента}
repeat
while mas[f] program
qsort
;
uses
crt
;
const
n
=
7
;
var
A
:
array
[
1..n
]
of
integer
;
first
,
last
,
i
:
integer
;
{
процедурасортировки}
procedure
quicksort
(var
mas
:
array
[
1..n
]
of
integer
;
first
,
last
:
integer
)
;
var
f
,
l
,
mid
,
count
:
integer
;
begin
f
:=
first
;
l
:=
last
;
mid
:=
mas
[
(f
+
l
)
div
2
]
;
{
вычислениеопорногоэлемента}
repeat
while
mas
[
f
]
<
mid
do
inc
(f
)
;
while
mas
[
l
]
>
mid
do
dec
(l
)
;
Алгоритмы и структуры данных для начинающих: сортировка Никита Прияцелюк В этой части мы посмотрим на пять основных алгоритмов сортировки данных в массиве. Начнем с самого простого - сортировки пузырьком - и закончим «быстрой сортировкой» (quicksort)
. Для каждого алгоритма, кроме объяснения его работы, мы также укажем его сложность по памяти и времени в наихудшем, наилучшем и среднем случае. Также смотрите другие материалы этой серии: , и . Для упрощения кода и улучшения читаемости мы введем метод Swap , который будет менять местами значения в массиве по индексу. Void Swap(T items, int left, int right)
{
if (left != right)
{
T temp = items;
items = items;
items = temp;
}
}
Сортировка пузырьком - это самый простой алгоритм сортировки. Он проходит по массиву несколько раз, на каждом этапе перемещая самое большое значение из неотсортированных в конец массива. Например, у нас есть массив целых чисел: При первом проходе по массиву мы сравниваем значения 3 и 7. Поскольку 7 больше 3, мы оставляем их как есть. После чего сравниваем 7 и 4. 4 меньше 7, поэтому мы меняем их местами, перемещая семерку на одну позицию ближе к концу массива. Теперь он выглядит так: Этот процесс повторяется до тех пор, пока семерка не дойдет почти до конца массива. В конце она сравнивается с элементом 8, которое больше, а значит, обмена не происходит. После того, как мы обошли массив один раз, он выглядит так: Поскольку был совершен по крайней мере один обмен значений, нам нужно пройти по массиву еще раз. В результате этого прохода мы перемещаем на место число 6. И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз. При следующем проходе обмена не производится, что означает, что наш массив отсортирован, и алгоритм закончил свою работу. Public void Sort(T items)
{
bool swapped;
do
{
swapped = false;
for (int i = 1; i < items.Length; i++) {
if (items.CompareTo(items[i]) > 0)
{
Swap(items, i - 1, i);
swapped = true;
}
}
} while (swapped != false);
}
Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее - нет. Важный момент: сортировка вставками обрабатывает элементы массива по порядку. Поскольку алгоритм проходит по элементам слева направо, мы знаем, что все, что слева от текущего индекса - уже отсортировано. На этом рисунке показано, как увеличивается отсортированная часть массива с каждым проходом: Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным. Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать: Алгоритм начинает работу с индекса 0 и значения 3. Поскольку это первый индекс, массив до него включительно считается отсортированным. На этом этапе элементы с индексами 0..1 отсортированы, а про элементы с индексами 2..n ничего не известно. Следующим проверяется значение 4. Так как оно меньше семи, мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex . Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки. Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так: Теперь часть массива, начиная от нулевого элемента и заканчивая элементом с индексом 2, отсортирована. Следующий проход начинается с индекса 3 и значения 4. По мере работы алгоритма мы продолжаем делать такие вставки. Когда больше нет возможностей для вставок, массив считается полностью отсортированным, и работа алгоритма закончена. Public void Sort(T items)
{
int sortedRangeEndIndex = 1;
while (sortedRangeEndIndex < items.Length)
{
if (items.CompareTo(items) < 0)
{
int insertIndex = FindInsertionIndex(items, items);
Insert(items, insertIndex, sortedRangeEndIndex);
}
sortedRangeEndIndex++;
}
}
private int FindInsertionIndex(T items, T valueToInsert)
{
for (int index = 0; index < items.Length; index++) {
if (items.CompareTo(valueToInsert) > 0)
{
return index;
}
}
throw new InvalidOperationException("The insertion index was not found");
}
private void Insert(T itemArray, int indexInsertingAt, int indexInsertingFrom)
{
// itemArray = 0 1 2 4 5 6 3 7
// insertingAt = 3
// insertingFrom = 6
//
// Действия:
// 1: Сохранить текущий индекс в temp
// 2: Заменить indexInsertingAt на indexInsertingFrom
// 3: Заменить indexInsertingAt на indexInsertingFrom в позиции +1
// Сдвинуть элементы влево на один.
// 4: Записать temp на позицию в массиве + 1.
// Шаг 1.
T temp = itemArray;
// Шаг 2.
itemArray = itemArray;
// Шаг 3.
for (int current = indexInsertingFrom; current > indexInsertingAt; current--)
{
itemArray = itemArray;
}
// Шаг 4.
itemArray = temp;
}
Сортировка выбором - это некий гибрид между пузырьковой и сортировкой вставками. Как и сортировка пузырьком, этот алгоритм проходит по массиву раз за разом, перемещая одно значение на правильную позицию. Однако, в отличие от пузырьковой сортировки, он выбирает наименьшее неотсортированное значение вместо наибольшего. Как и при сортировке вставками, упорядоченная часть массива расположена в начале, в то время как в пузырьковой сортировке она находится в конце. Давайте посмотрим на работу сортировки выбором на нашем неотсортированном массиве. При первом проходе алгоритм с помощью метода FindIndexOfSmallestFromIndex пытается найти наименьшее значение в массиве и переместить его в начало. Имея такой маленький массив, мы сразу можем сказать, что наименьшее значение - 3, и оно уже находится на правильной позиции. На этом этапе мы знаем, что на первой позиции в массиве (индекс 0) находится самое маленькое значение, следовательно, начало массива уже отсортировано. Поэтому мы начинаем второй проход - на этот раз по индексам от 1 до n – 1. На втором проходе мы определяем, что наименьшее значение - 4. Мы меняем его местами со вторым элементом, семеркой, после чего 4 встает на свою правильную позицию. Теперь неотсортированная часть массива начинается с индекса 2. Она растет на один элемент при каждом проходе алгоритма. Если на каком-либо проходе мы не сделали ни одного обмена, это означает, что массив отсортирован. После еще двух проходов алгоритм завершает свою работу: Public void Sort(T items)
{
int sortedRangeEnd = 0;
while (sortedRangeEnd < items.Length)
{
int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd);
Swap(items, sortedRangeEnd, nextIndex);
sortedRangeEnd++;
}
}
private int FindIndexOfSmallestFromIndex(T items, int sortedRangeEnd)
{
T currentSmallest = items;
int currentSmallestIndex = sortedRangeEnd;
for (int i = sortedRangeEnd + 1; i < items.Length; i++)
{
if (currentSmallest.CompareTo(items[i]) > 0)
{
currentSmallest = items[i];
currentSmallestIndex = i;
}
}
return currentSmallestIndex;
}
До сих пор мы рассматривали линейные алгоритмы. Они используют мало дополнительной памяти, но имеют квадратичную сложность. На примере сортировки слиянием мы посмотрим на алгоритм типа «разделяй и властвуй» (divide and conquer)
. Алгоритмы этого типа работают, разделяя крупную задачу на более мелкие, решаемые проще. Мы пользуемся ими каждый день. К примеру, поиск в телефонной книге - один из примеров такого алгоритма. Если вы хотите найти человека по фамилии Петров, вы не станете искать, начиная с буквы А и переворачивая по одной странице. Вы, скорее всего, откроете книгу где-то посередине. Если попадете на букву Т, перелистнете несколько страниц назад, возможно, слишком много - до буквы О. Тогда вы пойдете вперед. Таким образом, перелистывая туда и обратно все меньшее количество страниц, вы, в конце концов, найдете нужную. Насколько эффективны эти алгоритмы? Предположим, что в телефонной книге 1000 страниц. Если вы открываете ее на середине, вы отбрасываете 500 страниц, в которых нет искомого человека. Если вы не попали на нужную страницу, вы выбираете правую или левую сторону и снова оставляете половину доступных вариантов. Теперь вам надо просмотреть 250 страниц. Таким образом мы делим нашу задачу пополам снова и снова и можем найти человека в телефонной книге всего за 10 просмотров. Это составляет 1% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске. При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке. Давайте посмотрим на такой массив: Разделим его пополам: И будем делить каждую часть пополам, пока не останутся части с одним элементом: Теперь, когда мы разделили массив на максимально короткие участки, мы сливаем их в правильном порядке. Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив. Для работы алгоритма мы должны реализовать следующие операции: Стоит отметить, что в отличие от линейных алгоритмов сортировки, сортировка слиянием будет делить и склеивать массив вне зависимости от того, был он отсортирован изначально или нет. Поэтому, несмотря на то, что в худшем случае он отработает быстрее, чем линейный, в лучшем случае его производительность будет ниже, чем у линейного. Поэтому сортировка слиянием - не самое лучшее решение, когда надо отсортировать частично упорядченный массив. Public void Sort(T items)
{
if (items.Length <= 1)
{
return;
}
int leftSize = items.Length / 2;
int rightSize = items.Length - leftSize;
T left = new T;
T right = new T;
Array.Copy(items, 0, left, 0, leftSize);
Array.Copy(items, leftSize, right, 0, rightSize);
Sort(left);
Sort(right);
Merge(items, left, right);
}
private void Merge(T items, T left, T right)
{
int leftIndex = 0;
int rightIndex = 0;
int targetIndex = 0;
int remaining = left.Length + right.Length;
while(remaining > 0)
{
if (leftIndex >= left.Length)
{
items = right;
}
else if (rightIndex >= right.Length)
{
items = left;
}
else if (left.CompareTo(right) < 0)
{
items = left;
}
else
{
items = right;
}
targetIndex++;
remaining--;
}
}
Быстрая сортировка - это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги: Давайте посмотрим на работу алгоритма на следующем массиве: Сначала мы случайным образом выбираем ключевой элемент: Int pivotIndex = _pivotRng.Next(left, right);
Теперь, когда мы знаем ключевой индекс (4), мы берем значение, находящееся по этому индексу (6), и переносим значения в массиве так, чтобы все числа больше или равные ключевому были в правой части, а все числа меньше ключевого - в левой. Обратите внимание, что в процессе переноса значений индекс ключевого элемента может измениться (мы увидим это вскоре). Перемещение значений осуществляется методом partition . На этом этапе мы знаем, что значение 6 находится на правильной позиции. Теперь мы повторяем этот процесс для правой и левой частей массива. Мы рекурсивно вызываем метод quicksort на каждой из частей. Ключевым элементом в левой части становится пятерка. При перемещении значений она изменит свой индекс. Главное - помнить, что нам важно именно ключевое значение, а не его индекс. Снова применяем быструю сортировку: И еще раз: У нас осталось одно неотсортированное значение, а, поскольку мы знаем, что все остальное уже отсортировано, алгоритм завершает работу. Random _pivotRng = new Random();
public void Sort(T items)
{
quicksort(items, 0, items.Length - 1);
}
private void quicksort(T items, int left, int right)
{
if (left < right)
{
int pivotIndex = _pivotRng.Next(left, right);
int newPivot = partition(items, left, right, pivotIndex);
quicksort(items, left, newPivot - 1);
quicksort(items, newPivot + 1, right);
}
}
private int partition(T items, int left, int right, int pivotIndex)
{
T pivotValue = items;
Swap(items, pivotIndex, right);
int storeIndex = left;
for (int i = left; i < right; i++)
{
if (items[i].CompareTo(pivotValue) < 0)
{
Swap(items, i, storeIndex);
storeIndex += 1;
}
}
Swap(items, storeIndex, right);
return storeIndex;
}
На этом мы заканчиваем наш цикл статей по алгоритмам и структурам данных для начинающих. За это время мы рассмотрели связные списки, динамические массивы, двоичное дерево поиска и множества с примерами кода на C#. Цель: изучение алгоритма быстрой сортировки и ее модификаций. На этом занятии мы изучим алгоритм быстрой сортировки, который, пожалуй, используется более часто, чем любой другой. Основа алгоритма была разработана в 1960 году (C.A.R.Hoare) и с тех пор внимательно изучалась многими людьми. Быстрая сортировка особенно популярна ввиду легкости ее реализации; это довольно хороший алгоритм общего назначения, который хорошо работает во многих ситуациях, и использует при этом меньше ресурсов, чем другие алгоритмы. Основные достоинства этого алгоритма состоят в том, что он точечный (использует лишь небольшой дополнительный стек), в среднем требует только около N log N операций для того, чтобы отсортировать N элементов, и имеет экстремально короткий внутренний цикл. Недостатки алгоритма состоят в том, что он рекурсивен (реализация очень затруднена когда рекурсия недоступна), в худшем случае он требует N2 операций, кроме того он очень "хрупок": небольшая ошибка в реализации, которая легко может пройти незамеченной, может привести к тому, что алгоритм будет работать очень плохо на некоторых файлах. Производительность быстрой сортировки хорошо изучена. Алгоритм подвергался математическому анализу, поэтому существуют точные математические формулы касающиеся вопросов его производительности. Результаты анализа были неоднократно проверены эмпирическим путем, и алгоритм был отработан до такого состояния, что стал наиболее предпочтительным для широкого спектра задач сортировки. Все это делает алгоритм стоящим более детального изучения наиболее эффективных путей его реализации. Похожие способы реализации подходят также и для других алгоритмов, но в алгоритме быстрой сортировки мы можем использовать их с уверенностью, поскольку его производительность хорошо изучена. Улучшить алгоритм быстрой сортировки является большим искушением: более быстрый алгоритм сортировки - это своеобразная "мышеловка" для программистов. Почти с того момента, как Oia?a впервые опубликовал свой алгоритм, в литературе стали появляться "улучшенные" версии этого алгоритма. Было опробовано и проанализировано множество идей, но все равно очень просто обмануться, поскольку алгоритм настолько хорошо сбалансирован, что результатом улучшения в одной его части может стать более сильное ухудшение в другой его части. Мы изучим в некоторых деталях три модификации этого алгоритма, которые дают ему существенное улучшение. Хорошо же отлаженная версия быстрой сортировки скорее всего будет работать гораздо быстрее, чем любой другой алгоритм. Однако стоит еще раз напомнить, что алгоритм очень хрупок и любое его изменение может привести к нежелательным и неожиданным эффектам для некоторых входных данных. Суть алгоритма: число операций перемены местоположений элементов внутри массива значительно сократится, если менять местами далеко стоящие друг от друга элементы. Для этого выбирается для сравнения один элемент х, отыскивается слева первый элемент, который не меньше х, а справа первый элемент, который не больше х. Найденные элементы меняются местами. После первого же прохода все элементы, которые меньше х, будут стоять слева от х, а все элементы, которые больше х, - справа от х. С двумя половинами массива поступают точно также. Продолжая деление этих половин до тех пор пока не останется в них по 1 элементу. Program Quitsort;
uses
crt;
Const
N=10;
Type
Mas=array of integer;
var
a: mas;
k: integer;
function Part(l, r: integer):integer;
var
v, i, j, b: integer;
begin
V:=a[r];
I:=l-1;
j:=r;
repeat
repeat
dec(j)
until (a[j]<=v) or (j=i+1);
repeat
inc(i)
until (a[i]>=v) or (i=j-1);
b:=a[i];
a[i]:=a[j];
a[j]:=b;
until i>=j;
a[j]:=a[i];
a[i]:= a[r];
a[r]:=b;
part:=i;
end;
procedure QuickSort(l, t: integer);
var i: integer;
begin
if l 60,79, 82, 58, 39, 9, 54, 92, 44, 32
60,79, 82, 58, 39, 9, 54, 92, 44, 32
9,79, 82, 58, 39, 60, 54, 92, 44, 32
9,79, 82, 58, 39, 60, 54, 92, 44, 32
9, 32, 82, 58, 39, 60, 54, 92, 44, 79
9, 32, 44, 58, 39, 60, 54, 92, 82, 79
9, 32, 44, 58, 39, 54, 60, 92, 82, 79
9, 32, 44, 58, 39, 92, 60, 54, 82, 79
9, 32, 44, 58, 39, 54, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 60, 39, 54, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 58, 54, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 92, 82
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
"Внутренний цикл" быстрой сортировки состоит только из увеличения указателя и сравнения элементов массива с фиксированным числом. Это как раз и делает быструю сортировку быстрой. Сложно придумать более простой внутренний цикл. Положительные эффекты сторожевых ключей также оказывают здесь свое влияние, поскольку добавление еще одной проверки к внутреннему циклу оказало бы отрицательное влияние на производительность алгоритма. Самая сомнительная черта вышеприведенной программы состоит в том, что она очень мало эффективна на простых подфайлах. Например, если файл уже сортирован, то разделы будут вырожденными, и программа просто вызовет сама себя N раз, каждый раз с меньшим на один элемент подфайлом. Это означает, что не только производительность программы упадет примерно до N2/2, но и пространство необходимое для ее работы будет около N (смотри ниже), что неприемлемо. К счастью, есть довольно простые способы сделать так, чтобы такой "худший" случай не произошел при практическом использовании программы. Когда в файле присутствуют одинаковые ключи, то возникает еще два сомнительных вопроса. Первое, должны ли оба указателя останавливаться на ключах равных делящему элементу или останавливать только один из них, а второй будет проходить их все, или оба указателя должны проходить над ними. На самом деле, этот вопрос детально изучался, и результаты показали, что самое лучшее - это останавливать оба указателя. Это позволяет удерживать более или менее сбалансированные разделы в присутствии многих одинаковых ключей. На самом деле, эта программа может быть слегка улучшена терминированием сканирования j Характеристики Производительности Быстрой Сортировки Самое лучшее, что могло бы произойти для алгоритма - это если бы каждый из подфайлов делился бы на два равных по величине подфайла. В результате количество сравнений делаемых быстрой сортировкой было бы равно значению рекурсивного выражения CN = 2CN/2+N - наилучший случай. (2CN/2 покрывает расходы по сортировке двух полученных подфайлов; N - это стоимость обработки каждого элемента, используя один или другой указатель.) Нам известно также, что примерное значение этого выражения равно CN = N lg N. Хотя мы встречаемся с подобной ситуацией не так часто, но в среднем время работы программы будет соответствовать этой формуле. Если принять во внимание вероятные позиции каждого раздела, то это сделает вычисления более сложными, но конечный результат будет аналогичным. Свойство 1 Быстрая сортировка в среднем использует 2N ln N сравнений. Методы улучшения быстрой сортировки. Первое улучшение в алгоритме быстрой сортировки возникает из наблюдения, что программа гарантировано вызывает себя для огромного количества небольших подфайлов, поэтому следует использовать самый лучший метод сортировки когда мы встречаем небольшой подфайл. Очевидный способ добиться этого, это изменить проверку в начале рекурсивной функции из "if r>l then" на вызов сортировки вставкой (соответственно измененной для восприятия границ сортируемого подфайла): "if r-l<=M then insertion(l, r)." Значение для M не обязано быть "самым-самым" лучшим: алгоритм работает примерно одинаково для M от 5 до 25. Время работы программы при этом снижается примерно на 20% для большинства программ. При небольших подфайлах (5- 25 элементов) быстрая сортировка очень много раз вызывает сама себя (в наше примере для 10 элементов она вызвала сама себя 15 раз), поэтому следует применять не быструю сортировку, а сортировку вставкой. Procedure QuickSort (l,t:integer);
var
i:integer;
begin
if t-l>m then
begin
i:=part(l,t);
QuickSort (l,i-1);
QuickSort (i+1,t);
end
Else
Insert(l,t);
end;
Второе улучшение в алгоритме быстрой сортировки состоит в попытке использования лучшего делящего элемента. У нас есть несколько возможностей. Наиболее безопасная из них будет попытка избежать худшего случая посредством выбора произвольного элемента массива в качестве делящего элемента. Тогда вероятность худшего случая становится пренебрежимо мала. Это простой пример "вероятностного" алгоритма, который почти всегда работает вне зависимости от входных данных. Произвольность может быть хорошим инструментом при разработке алгоритмов, особенно если возможны подозрительные входные данные. Более полезное улучшение состоит в том, чтобы взять из файла три элемента, и затем использовать среднее из них в качестве делящего элемента. Если элементы взяты из начала, середины, и конца файла, то можно избежать использования сторожевых элементов: сортируем взятые три элемента, затем обмениваем центральный элемент с a, и затем используем алгоритм деления на массиве a. Это улучшение называется делением по медиане из трех. Метод деления по медиане из трех полезен по трем причинам. Во-первых, он делает вероятность худшего случая гораздо более низкой. Чтобы этот алгоритм использовал время пропорциональной N2, два из трех взятых элементов должны быть либо самыми меньшими, либо самыми большими, и это должно повторяться из раздела в раздел. Во-вторых, этот метод уничтожает необходимость в сторожевых элементах, поскольку эту роль играет один из трех взятых нами перед делением элементов. В третьих, он на самом деле снижает время работы алгоритма приблизительно на 5%. Procedure exchange(i,j:integer);
var
k:integer;
begin
k:=a[i];
a[i]:=a[j];
a[j]:=k;
end;
procedure Mediana;
var i:integer;
begin
i:=n div 4;{Рис.}
if a[i]>a then
if a[i]>a then
exchange(i,n)
else
exchange(i*3,n)
else
if a>a then
exchange(i*2,n);
quicksort(1,n);
end;
Можно переписать данный алгоритм без использования рекурсии используя стек, но здесь мы это не будем делать. Комбинация нерекурсивной реализации деления по медиане из трех с отсечением на небольшие файлы может улучшить время работы алгоритма от 25% до 30%. Итак, на сегодняшнем занятии мы рассмотрели алгоритм быстрой сортировки. На сегодняшнем занятии мы начнем рассмотрении темы внешняя сортировка. Внешняя сортировка сортирует файлы, которые не помещаются целиком в оперативную память. Внешняя сортировка сильно отличается от внутренней. Дело в том, что доступ к файлу является последовательным, а не параллельным как это было в массиве. И поэтому считывать файл можно только блоками и этот блок отсортировать в памяти и снова записать в файл. Принципиальную возможность эффективно отсортировать файл, работая с его частями и не выходя за пределы части обеспечивает алгоритм слияния. Под слиянием понимается объединение двух (или более) упорядоченных последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Слияние - намного более простая операция, чем сортировка. Мы рассмотрим 2 алгоритма слияния: Последовательность а разбивается на две половины b и с. Последовательности b и с сливаются при помощи объединения отдельных элементов в упорядоченные пары. Полученной последовательности присваивается имя а, после чего повторяются шаги 1 и 2; при этом упорядоченные пары сливаются в упорядоченные четверки. Предыдущие шаги повторяются, при этом четверки сливаются в восьмерки и т.д., пока не будет упорядочена вся последовательность, т.к. длины последовательностей каждый раз удваиваются. Пример
Исходная последовательность А = 44 55 12 42 94 18 06 67
1
b = 44 55 12 42
с = 94 18 06 67
а = 44 94" 18 55" 06 12" 42 67
2
b = 44 94" 18 55"
с =06 12" 42 67
а = 06 12 44 94" 18 42 55 67"
3
b = 06 12 44 94"
с = 18 42 55 67"
а = 06 12 18 42 44 55 67 94
Операция, которая однократно обрабатывает всё множество данных, называется фазой. Наименьший подпроцесс, который, повторяясь, образует процесс сортировки, называется проходом или этапом. В нашем примере сортировка производится за три прохода. Каждый проход состоит из фазы разбиения и фазы слияния. Главным минусом сортировки слиянием является удвоение размера памяти, первоначально занятой сортируемыми данными. Рассмотрим алгоритм с рекурсивным актом слияния, предложенный Боузом и Нельсоном и не требующий резерва памяти. Он основан на очевидной идее: слить две равные упорядоченные части можно слиянием их начальных половин, слиянием конечных и слиянием 2-й половины 1-го результата с 1-й половиной 2-го результата, например: Если части не равны или не делятся точно пополам, процедуру уточняют надлежащим образом. Аналогично слияние "половинок" можно свести к слиянию "четвертушек", "восьмушек" и т. д.; имеет место рекурсия. Const n=200;
Type
tipkl=word;
tip = Record
kl: tipkl;
z:Array of real
End;
Var
A: Array of tip;
j:word;
Procedure Bose (Var AA; voz:Boolean);
Var
m,j:word; x:tip; {tip - тип сортируемых записей}
A: Array of tip Absolute AA;
Procedure Sli(j,r,m: word); { r - расстояние между началами
сливаемых частей, а m - их размер, j - наименьший номер записи}
Begin
if j+r<=n Then
If m=1 Then
Begin
If voz Xor (A[j].kl < A.kl) Then
Begin
x:=A[j];
A[j]:= A;
A:=x
End
End
Else
Begin
m:=m div 2;
Sli(j,r,m); {Слияние "начал"}
If j+r+m<=n Then
Sli(j+m,r,m); {Слияние "концов"}
Sli(j+m,r-m,m) End {Слияние в центральной части}
End{блока Sli};
Begin
m:=1;
Repeat
j:=1; {Цикл слияния списков равного размера: }
While j+m<=n do
Begin
Sli(j,m,m);
j:=j+m+m
End;
m:=m+m {Удвоение размера списка перед началом нового прохода}
Until m >= n {Конец цикла, реализующего все дерево слияний}
End{блока Bose};
BEGIN
Randomize;
For j:=1 to n do
begin
A[j].kl:= Random(65535);
Write(A[j].kl:8);
end;
Readln;
Bose(A,true);
For j:=1 to n do
Write(A[j].kl:8);
Readln
END.
Она объединяются упорядоченные части, спонтанно возникшие в исходном массиве; они могут быть также следствием предыдущей обработки данных. Рассчитывать на одинаковый размер сливаемых частей не приходится. Записи, идущие в порядке неубывания ключей, сцепляются, образуя подсписок. Минимальный подсписок одна запись. Пример:
Пусть даны ключи записей 5 7 8 3 9 4 1 7 6
Ищем подсписки В один общий список соединяются 1-й, 3-й, 5-й и т. д. подсписки, в другой - 2-й, 4-й и т. д. подсписки. Произведем слияние 1 подсписка 1 списка и 1 подсписка 2 списка, 2 подсписка 1 списка и 2 подсписка 2 списка и т.д. Будут получены следующие цепи 3 --> 5 --> 7 --> 8 --> 9 и 1 --> 4 --> 7
Подсписок, состоящий из записи "6", пары не имеет и "принудительно" объединяется с последней цепью, принимающей вид 1 --> 4--> 6 --> 7. При нашем небольшом числе записей 2-й этап, на котором сливаются две цепи, окажется последним. В общем случае на каждом этапе подсписок - результат слияния начальных подсписков 1 и 2 списка становится началом нового 1-го списка, а результат слияния следующих двух подсписков - началом 2-го списка. Следующие образуемые подсписки поочередно включаются в 1-й и во 2-й список. Для программной реализации заводят массив sp: элемент sp[i] - это номер записи, которая следует за i-й. Последняя запись одного подсписка ссылается на первую запись другого, а для различения концов подсписков эта ссылка снабжается знаком минус. Repeat {Повторение актов слияний подсписков}
If A[j].kl < A[i].kl Then {Выбирается меньшая запись}
Begin sp[k]:=j; k:=j; j:=sp[j];
If j<=0 Then {Сцепление с остатком "i"-подсписка}
Begin sp[k]:=i; Repeat m:=i; i:=sp[i] Until i<=0 End
End
Else
Begin sp[k]:=i; k:=i; i:=sp[i];
If i<=0 Then {Сцепление с остатком "j"-подсписка}
Begin sp[k]:=j; Repeat m:=j; j:=sp[j] Until j<=0 End
End;
If j<=0 Then Begin sp[m]:= 0; sp[p]:=-sp[p]; i:=-i;
j:=-j; If j<>0 Then p:=r; k:=r; r:=m End
Until j=0;
{В конец сформированного подсписка всегда заносится нулевая ссылка (sp[m]:= 0), ибо он может оказаться последним. Действие sp[p]:= -sp[p] обозначает минусом конец ранее построенного подсписка. Итак, на сегодняшнем занятии мы рассмотрели алгоритмы слияния.
Метод Swap
Пузырьковая сортировка
Сортировка вставками
Сортировка выбором
Сортировка слиянием
Разделяй и властвуй
Сортировка слиянием
Быстрая сортировка
Заключение
1. Небольшие Подфайлы.
2. Деление по Медиане из Трех
3. Нерекурсивная реализация.
Слияние
Прямое слияние. Алгоритм Боуза - Нельсона
Естественное (Неймановское) слияние.