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

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

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

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

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

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

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