Быстрая сортировка как метод программирования

Видео: Java - алгоритмы: Сортировка методом Шелла!

В 1960 году К. А. Хоар разработал метод быстрой сортировки информации, ставший самым известным. На сегодняшний день он широко применяется в программировании, так как имеет массу положительных свойств: может использоваться для общих случаев, требует небольшого увеличения дополнительной памяти, совместим с разными типами списков и удобен для реализации. Но есть и недостатки, которыми обладает быстрая сортировка: при использовании в работе допускается много ошибок и она несколько неустойчива.

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

Быстрая сортировка очень распространена, ее можно встретить везде. На ее основе реализован метод TList.Sort, существующий во всех версиях (за исключением 1) Delphi, функция библиотеки времени, затраченного на выполнение, qsort в C++.

Основной принцип работы можно сформулировать как "разделяй и властвуй". Происходит разбитие списка на две группы и сортировка выполняется для каждой части сама по себе. Отсюда следует, что большее внимание требуется уделять процессу разделения, во время которого происходит следующее: определяется базовый элемент и уже относительно него переставляется весь список. Левее выстраивается группа кандидатов, значения которых меньше, правее переносятся все другие. Получается, что основной элемент в отсортированном списке расположен на своем законном месте. Дальнейший этап – это вызов рекурсивной функции сортировки для обеих сторон элементов относительно базового. Заканчивается процесс работы только тогда, когда список будет содержать только один элемент, то есть будет отсортированным. Таким образом, чтобы освоить такую функцию программирования, как быстрая сортировка, надо знать работу алгоритмов более низкого уровня: а) выбор базового элемента- б) наиболее эффективная перестановка списка для получения двух наборов с меньшими и большими значениями.

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

Видео: Быстрая сортировка C/C++

После того, как с выбором определились, можно переходить к работе алгоритма разбиения. Это так называемые внутренние циклы быстрой сортировки. Все строится на двух быстроработающих индексах: первый пойдет по элементам слева направо, второй, наоборот, справа налево. Начинается операция выполнения справа: индекс идет по списку и сравнивает все значения с основным. Цикл считается завершенным, если находится элемент меньший или равный базовому. То есть происходит сравнение и уменьшается значение индекса. С левой стороны работа закончена при нахождении большего или равного значения. И здесь значение при сравнении увеличивается.

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