За линейное время можно сортировать только массивы, на элементы которых наложены дополнительные ограничения: например, элементы принадлежат фиксированному числу видов.
8.5.1. Задача "Красные и белые"
В этой задаче элементы массива принадлежат двум видам - они либо красные, либо белые. Отсортировать такой массив можно за линейное время, более того, за один проход по массиву, выполняя не более одной проверки и одного обмена для каждого элемента массива. Задача разбиения массива на два подмножества в той или иной формулировке часто встречается в практике программирования. В частности, она возникает в алгоритме быстрой сортировки Хоара.
Все множество индексов элементов массива разделим на три непересекающихся подмножества: 0 - зона, содержащая только белые элементы; непроверенная зона для тех элементов, чей цвет не установлен; 1- зона для красных элементов. Инвариантом, поддерживаемым в проектируемом алгоритме, будет расположение зон. Массив отсортирован, когда непроверенная зона становится пустой. В этом идея алгоритма - поддерживать истинность инварианта, сокращая непроверенную зону. В начальном состоянии 0-зона и 1-зона пусты, а непроверенная зона занимает все множество индексов, так что ее начальная граница Start = 0, а граница Finish = n-1. В начальном состоянии инвариант считается истинным. Основной и единственный проход по циклу выполняется по непроверенной зоне до тех пор, пока эта зона не станет пустой (или не будет состоять из одного элемента). Проверка элементов начинается с левого конца непроверенной зоны. До тех пор, пока очередной элемент является белым, расширяется 0-зона и соответственно сокращается непроверенная зона - значение границы Start увеличивается на 1. В тот момент, когда встречается красный элемент, проверка прекращается и запускается аналогичный цикл, но теперь уже с правого конца непроверенной зоны. Когда на правом конце обнаруживается белый элемент, происходит обмен значениями на двух концах непроверенной зоны. Обмен восстанавливает истинность инварианта. По завершении цикла непроверенная зона становится пустой, так что 1-зона с красными элементами следует сразу за 0-зоной с белыми элементами и массив отсортирован.
8.5.2. Задача Дейкстры "О голландском национальном флаге"
Эдсгар Дейкстра рассматривал эту задачу в своей известной книге по структурному программированию. Элементы в массиве принадлежат трем видам - красные, белые и синие. Требуется отсортировать массив в порядке следования этих цветов во флаге Голландии. Поскольку цвета флагов России и Голландии совпадают, то для нас приятнее сортировать массив в порядке следования этих цветов во флаге России - белые, синие, красные элементы.
Алгоритм сортировки за один проход по массиву нетрудно получить обобщением предыдущего алгоритма. Рассмотрим массив, состоящий из четырех зон: 0-зоны, содержащей только белые элементы, 1-зоны с синими элементами, непроверенной зоны и 2-зоны с красными элементами. Инвариантом, поддерживаемым в алгоритме, является расположение зон. В начальный момент все зоны, кроме непроверенной, пусты и инвариант считается истинным. Внешний цикл по-прежнему идет по элементам непроверенной зоны, продвигаясь попеременно то слева, то справа. При движении слева, пока встречаются синие элементы, расширяется синяя зона. Если встретился не синий элемент, то он может быть либо белым, либо красным. Если это белый элемент, то он меняется местами с первым элементом, начинающим синюю зону. После чего проверка продолжается с левого конца непроверенной зоны. Когда же встречается красный элемент, то непроверенная зона начинает проверяться с правого конца. Когда при проверке справа встречается не красный элемент, то происходит обмен с красным элементом, найденным при проверке слева. Если справа был обнаружен белый элемент, то понадобится еще один обмен, чтобы поставить его на свое место.
Все операции поддерживают истинность инварианта. Когда цикл завершается и непроверенная зона становится пустой, массив отсортирован.
8.5.3. Задача Гарри Поттера "Сортировочная шляпа"
Задачи, где в массиве 4 вида элементов, встречаются не менее часто. Например, молекула ДНК, как уже упоминалось, представляется строкой (массивом char) в алфавите из четырех символов. Этот массив иногда требуется отсортировать в некотором заданном порядке следования символов. Приведу следующую содержательную постановку этой задачи.
В школу чародейства и волшебства Хогвартс прибыли новые ученики числом N. Их посадили за один стол в произвольном порядке. Сортирующая шляпа рассортировала учеников и рассадила их по своим классам - слева направо: Гриффиндор, Рэйвенкло, Хаффлпафф, Слизерин.
В процессе сортировки сортирующая шляпа каждый раз выбирала одного из учеников (каждый выбирался только один раз) и определяла класс, к которому должен принадлежать данный ученик, после чего под руководством сортирующей шляпы при необходимости выполнялся один или несколько обменов местами учеников.
Сортирующая шляпа пользовалась эффективным алгоритмом сортировки, являющимся обобщением алгоритма Дейкстры. Случай 4-х элементов восстанавливает симметрию расположения зон - по две зоны справа и слева от непроверенной зоны. В этом случае анализ на левом и правом конце непроверенной зоны выполняется одинаковым образом.
