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