Алгоритмы и структуры данных для начинающих: сортировка

Никита Прияцелюк

В этой части мы посмотрим на пять основных алгоритмов сортировки данных в массиве. Начнем с самого простого - сортировки пузырьком - и закончим «быстрой сортировкой» (quicksort) .

Для каждого алгоритма, кроме объяснения его работы, мы также укажем его сложность по памяти и времени в наихудшем, наилучшем и среднем случае.

Также смотрите другие материалы этой серии: , и .

Метод Swap

Для упрощения кода и улучшения читаемости мы введем метод 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% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске.

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

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

Давайте посмотрим на такой массив:

Разделим его пополам:

И будем делить каждую часть пополам, пока не останутся части с одним элементом:

Теперь, когда мы разделили массив на максимально короткие участки, мы сливаем их в правильном порядке.

Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив.

Для работы алгоритма мы должны реализовать следующие операции:

1. Операцию для рекурсивного разделения массива на группы (метод Sort).
2. Слияние в правильном порядке (метод Merge).

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

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--; } }

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

Быстрая сортировка - это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги:

1. Выбрать ключевой индекс и разделить по нему массив на две части. Это можно делать разными способами, но в данной статье мы используем случайное число.
2. Переместить все элементы больше ключевого в правую часть массива, а все элементы меньше ключевого - в левую. Теперь ключевой элемент находится в правильной позиции - он больше любого элемента слева и меньше любого элемента справа.
3. Повторяем первые два шага, пока массив не будет полностью отсортирован.

Давайте посмотрим на работу алгоритма на следующем массиве:

Сначала мы случайным образом выбираем ключевой элемент:

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#.

Обновлено: 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 возвращает индекс опорного елемента, который делит массив на элементы меньше опорного слева, и элементы больше опорного справа. В самом методе в качестве опорного выбирается последний элемент, а обход осуществляется от начала массива.

O(n ) вспомогательных
O(log n ) вспомогательных (Седжвик 1978)

Быстрая сортировка , сортировка Хоара (англ. quicksort ), часто называемая qsort (по имени в стандартной библиотеке языка Си) - широко известный алгоритм сортировки , разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году .

algorithm quicksort(A, lo, hi) is if lo < hi then p:= partition(A, lo, hi) quicksort(A, lo, p – 1) quicksort(A, p + 1, hi) algorithm partition(A, lo, hi) is pivot:= A i:= lo - 1 for j:= lo to hi - 1 do if A[j] ≤ pivot then i:= i + 1 swap A[i] with A[j] swap A with A return i + 1

Сортировка всего массива может быть выполнена с помощью выполнения quicksort(A, 1, length(A)) .

Разбиение Хоара

Данная схема использует два индекса (один в начале массива, другой в конце), которые приближаются друг к другу, пока не найдётся пара элементов, где один больше опорного и расположен перед ним, а второй меньше и расположен после. Эти элементы меняются местами. Обмен происходит до тех пор, пока индексы не пересекутся. Алгоритм возвращает последний индекс. . Схема Хоара эффективнее схемы Ломуто, так как происходит в среднем в три раза меньше обменов (swap) элементов, и разбиение эффективнее, даже когда все элементы равны. Подобно схеме Ломуто, данная схема также показывает эффективность в O (n 2) , когда входной массив уже отсортирован. Сортировка с использованием данной схемы нестабильна. Следует заметить, что конечная позиция опорного элемента необязательно совпадает с возвращённым индексом. Псевдокод :

algorithm quicksort(A, lo, hi) is if lo < hi then p:= partition(A, lo, hi) quicksort(A, lo, p) quicksort(A, p + 1, hi) algorithm partition(A, lo, hi) is pivot:= A i:= lo - 1 j:= hi + 1 loop forever do i:= i + 1 while A[i] < pivot do j:= j - 1 while A[j] > pivot if i >= j then return j swap A[i] with A[j]

Повторяющиеся элементы

Для улучшения производительности при большом количестве одинаковых элементов в массиве может быть применена процедура разбиения массива на три группы: элементы меньшие опорного, равные ему и больше него. (Бентли и Макилрой называют это «толстым разбиением». Данное разбиение используется в функции qsort в седьмой версии Unix . ). Псевдокод:

algorithm quicksort(A, lo, hi) is if lo < hi then p:= pivot(A, lo, hi) left, right:= partition(A, p, lo, hi) // возвращается два значения quicksort(A, lo, left) quicksort(A, right, hi)

Оценка сложности алгоритма

Ясно, что операция разделения массива на две части относительно опорного элемента занимает время . Поскольку все операции разделения, проделываемые на одной глубине рекурсии, обрабатывают разные части исходного массива, размер которого постоянен, суммарно на каждом уровне рекурсии потребуется также O (n) {\displaystyle O(n)} операций. Следовательно, общая сложность алгоритма определяется лишь количеством разделений, то есть глубиной рекурсии. Глубина рекурсии, в свою очередь, зависит от сочетания входных данных и способа определения опорного элемента.

Лучший случай. В наиболее сбалансированном варианте при каждой операции разделения массив делится на две одинаковые (плюс-минус один элемент) части, следовательно, максимальная глубина рекурсии, при которой размеры обрабатываемых подмассивов достигнут 1, составит log 2 ⁡ n {\displaystyle \log _{2}n} . В результате количество сравнений, совершаемых быстрой сортировкой, было бы равно значению рекурсивного выражения C n = 2 ⋅ C n / 2 + n {\displaystyle C_{n}=2\cdot C_{n/2}+n} , что даёт общую сложность алгоритма O (n ⋅ log 2 ⁡ n) {\displaystyle O(n\cdot \log _{2}n)} . Среднее. Среднюю сложность при случайном распределении входных данных можно оценить лишь вероятностно. Прежде всего необходимо заметить, что в действительности необязательно, чтобы опорный элемент всякий раз делил массив на две одинаковых части. Например, если на каждом этапе будет происходить разделение на массивы длиной 75 % и 25 % от исходного, глубина рекурсии будет равна , а это по-прежнему даёт сложность . Вообще, при любом фиксированном соотношении между левой и правой частями разделения сложность алгоритма будет той же, только с разными константами. Будем считать «удачным» разделением такое, при котором опорный элемент окажется среди центральных 50 % элементов разделяемой части массива; ясно, вероятность удачи при случайном распределении элементов составляет 0,5. При удачном разделении размеры выделенных подмассивов составят не менее 25 % и не более 75 % от исходного. Поскольку каждый выделенный подмассив также будет иметь случайное распределение, все эти рассуждения применимы к любому этапу сортировки и любому исходному фрагменту массива. Удачное разделение даёт глубину рекурсии не более log 4 / 3 ⁡ n {\displaystyle \log _{4/3}n} . Поскольку вероятность удачи равна 0,5, для получения k {\displaystyle k} удачных разделений в среднем потребуется 2 ⋅ k {\displaystyle 2\cdot k} рекурсивных вызовов, чтобы опорный элемент k раз оказался среди центральных 50 % массива. Применяя эти соображения, можно заключить, что в среднем глубина рекурсии не превысит 2 ⋅ log 4 / 3 ⁡ n {\displaystyle 2\cdot \log _{4/3}n} , что равно O (log ⁡ n) {\displaystyle O(\log n)} А поскольку на каждом уровне рекурсии по-прежнему выполняется не более O (n) {\displaystyle O(n)} операций, средняя сложность составит O (n log ⁡ n) {\displaystyle O(n\log n)} . Худший случай. В самом несбалансированном варианте каждое разделение даёт два подмассива размерами 1 и , то есть при каждом рекурсивном вызове больший массив будет на 1 короче, чем в предыдущий раз. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых. При простейшем выборе опорного элемента - первого или последнего в массиве, - такой эффект даст уже отсортированный (в прямом или обратном порядке) массив, для среднего или любого другого фиксированного элемента «массив худшего случая» также может быть специально подобран. В этом случае потребуется n − 1 {\displaystyle n-1} операций разделения, а общее время работы составит ∑ i = 0 n (n − i) = O (n 2) {\displaystyle \textstyle \sum _{i=0}^{n}(n-i)=O(n^{2})} операций, то есть сортировка будет выполняться за квадратичное время. Но количество обменов и, соответственно, время работы - это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти (переполнению стека) во время работы программы.

Достоинства и недостатки

Достоинства:

Недостатки:

Улучшения

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

• Проблема неустойчивости решается путём расширения ключа исходным индексом элемента в массиве. В случае равенства основных ключей сравнение производится по индексу, исключая, таким образом, возможность изменения взаимного положения равных элементов. Эта модификация не бесплатна - она требует дополнительно O(n) памяти и одного полного прохода по массиву для сохранения исходных индексов.

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

• Выбор среднего элемента. Устраняет деградацию для предварительно отсортированных данных, но оставляет возможность случайного появления или намеренного подбора «плохого» массива.
• Выбор медианы из трёх элементов: первого, среднего и последнего. Снижает вероятность возникновения худшего случая, по сравнению с выбором среднего элемента.
• Случайный выбор. Вероятность случайного возникновения худшего случая становится исчезающе малой, а намеренный подбор - практически неосуществимым. Ожидаемое время выполнения алгоритма сортировки составляет O(n lg n ).

Недостаток всех усложнённых методов выбора опорного элемента - дополнительные накладные расходы; впрочем, они не так велики.

• Во избежание отказа программы из-за большой глубины рекурсии могут применяться следующие методы:

	Имеется викиучебник по теме «Примеры реализации быстрой сортировки »

Выбирая алгоритм сортировки для практических целей, программист, вполне вероятно, остановиться на методе, называемом «Быстрая сортировка» (также «qsort» от англ. quick sort). Его разработал в 1960 году английский ученый Чарльз Хоар, занимавшийся тогда в МГУ машинным переводом. Алгоритм, по принципу функционирования, входит в класс обменных сортировок (сортировка перемешиванием, пузырьковая сортировка и др.), выделяясь при этом высокой скоростью работы.

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

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

Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:

• разбиение массива относительно опорного элемента;
• рекурсивная сортировка каждой части массива.

Разбиение массива.

Еще раз об опорном элементе. Его выбор не влияет на результат, и поэтому может пасть на произвольный элемент. Тем не менее, как было замечено выше, наибольшая эффективность алгоритма достигается при выборе опорного элемента, делящего последовательность на равные или примерно равные части. Но, как правило, из-за нехватки информации не представляется возможности наверняка определить такой элемент, поэтому зачастую приходиться выбирать опорный элемент случайным образом.

В следующих пяти пунктах описана общая схема разбиения массива (сортировка по возрастанию):

1. вводятся указатели first и last для обозначения начального и конечного элементов последовательности, а также опорный элемент mid ;
2. вычисляется значение опорного элемента (first +last )/2, и заноситься в переменную mid ;
3. указатель first смещается с шагом в 1 элемент к концу массива до тех пор, пока Mas [first ]>mid . А указатель last смещается от конца массива к его началу, пока Mas [last ]<mid ;
4. каждые два найденных элемента меняются местами;
5. пункты 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 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]; //вычисление опорного элемента do { while (mas[f]mid) l--; if (f<=l) //перестановка элементов { count=mas[f]; mas[f]=mas[l]; mas[l]=count; f++; l--; } } while (f>void"); }

#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]mid do dec(l); if f<=l then {перестановка элементов} begin count:=mas[f]; mas[f]:=mas[l]; mas[l]:=count; inc(f); dec(l); end; until f>l; if first

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 ) ;

Всем привет! Я расскажу об алгоритме быстрой сортировки и покажу, как его можно реализовать программно.

Итак, быстрая сортировка, или, по названию функции в Си, Qsort - это алгоритм сортировки, сложность которого в среднем составляет O(n log(n)). Суть его предельно проста: выбирается так называемый опорный элемент, и массив делится на 3 подмассива: меньших опорного, равных опорному и больших опорного. Потом этот алгоритм применяется рекурсивно к подмассивам.

Алгоритм

1. Выбираем опорный элемент
2. Разбиваем массив на 3 части
   • Создаём переменные l и r - индексы соответственно начала и конца рассматриваемого подмассива
   • Увеличиваем l, пока l-й элемент меньше опорного
   • Уменьшаем r, пока r-й элемент больше опорного
   • Если l всё ещё меньше r, то меняем l-й и r-й элементы местами, инкрементируем l и декрементируем r
   • Если l вдруг становится больше r, то прерываем цикл
3. Повторяем рекурсивно, пока не дойдём до массива из 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