635
правок
Изменения
→Быстрая сортировка с разделением на три части
===Быстрая сортировка с разделением на три части===
Когда в сортируемом файле имеется множество дублированных ключей предыдущие реализации быстрой сортировки можно существенно улучшить. Например массив, который состоит из равных ключей, вовсе не нуждается в дальнейшей сортировке, однако предыдущие реализации продолжают процесс разделения, подвергая обработке все более мелкие подфайлы независимо от того, насколько большим является исходный файл.
В основу программы положено разделение массива на три части:
на элементы,меньшие разделяющего элемента (в позиции а[l].. a[j]),
элементы, равные разделяющему элементу (в позиции a[j+1],..., a[i-1]),
и элементы большие разделяющего элемента (в позиции a[i],..., a[r]).
После этого сортировка завершается двумя рекурсивными вызовами.
Просмотр массива начинается слева с целью обнаружить элемент, который не меньше разделяющего элемента, и справа с целью обнаружить элемент, который не больше разделяющего элемента, затем они меняются местами. Если после обмена элемент слева равен разделяющему элементу, он меняется местами с левым
крайним элементом массива; то же самое проделывается и справа.
После того как указатели пересекутся, элементы, равные разделяющему элементу и находящиеся на разных концах массива, после операции обмена попадают в свои
окончательные позиции. После этого указанные ключи могут быть исключены из подфайлов, для которых выполняются последующие рекурсивные вызовы.
'''void''' quicksort(a: '''int'''[n], '''int''' l, '''int''' r):
