Проблема голландского национального флага

Вычислительная задача о сортировке

Задача о голландском национальном флаге ^[1] — вычислительная задача , предложенная Эдсгером Дейкстрой . ^[2] Флаг Нидерландов состоит из трех цветов: красного, белого и синего. Имея шары этих трех цветов, расположенные случайным образом в ряд (неважно, сколько шаров), задача состоит в том, чтобы расположить их так, чтобы все шары одного цвета были вместе, а их общие цветовые группы находились в правильном порядке.

Решение этой проблемы представляет интерес для проектирования алгоритмов сортировки ; в частности, варианты алгоритма быстрой сортировки , которые должны быть устойчивы к повторяющимся элементам, могут использовать трехстороннюю функцию разбиения, которая группирует элементы, меньшие заданного ключа (красный), равные ключу (белый) и большие ключа (синий). Существует несколько решений, которые имеют различные характеристики производительности, адаптированные для сортировки массивов с малым или большим количеством повторяющихся элементов. ^[3]

Случай массива

Эту проблему также можно рассматривать с точки зрения перестановки элементов массива . Предположим, что каждый из возможных элементов можно отнести только к одной из трех категорий (нижний, средний и верхний). Например, если все элементы находятся в диапазоне 0 ... 1, то нижний элемент можно определить как элементы в диапазоне 0 ... 0,25 (не включая 0,25), средний элемент как 0,25 ... 0,5 (не включая 0,5), а верхний элемент как 0,5 и больше. (Выбор этих значений показывает, что категории не обязательно должны быть равными диапазонами). Тогда проблема заключается в том, чтобы создать массив таким образом, чтобы все «нижние» элементы располагались перед (имели индекс меньше индекса) всеми «средними» элементами, которые располагаются перед всеми «верхними» элементами.

Один алгоритм заключается в том, чтобы верхняя группа росла вниз от вершины массива, нижняя группа росла вверх от основания, а средняя группа оставалась чуть выше основания. Алгоритм индексирует три местоположения: низ верхней группы, верх нижней группы и верх средней группы. Элементы, которые еще предстоит отсортировать, попадают между средней и верхней группами. ^[4] На каждом шаге проверяйте элемент чуть выше середины. Если он принадлежит верхней группе, поменяйте его местами с элементом чуть ниже вершины. Если он принадлежит нижней группе, поменяйте его местами с элементом чуть выше основания. Если он находится в середине, оставьте его. Обновите соответствующий индекс. Сложность составляет Θ(n) ходов и проверок. ^[1]

Псевдокод

Следующий псевдокод для трехстороннего разбиения, который предполагает индексацию массива с нуля, был предложен самим Дейкстрой. ^[2] Он использует три индекса $i$ , $j$ и $k$ , сохраняя инвариант, что $i \leq j \leq k$ .

Записи от 0 до (но не включая) $i$ — это значения меньше $mid$ ,
Записи от $i$ до (но не включая) $j$ имеют значения, равные $mid$ ,
записи от $j$ до (включительно) $k$ — это значения, которые еще не отсортированы, и
Элементы от $k + 1$ до конца массива имеют значения больше $mid$ .

процедура трехстороннего разбиения (A: массив значений, середина: значение): я ← 0 ж ← 0 k ← размер A - 1 пока j <= k: если A[j] < mid: поменять местами A[i] и A[j] я ← я + 1 й ← й + 1 иначе, если A[j] > mid: поменять местами A[j] и A[k] к ← к - 1 еще : й ← й + 1

Смотрите также

Ссылки

^ ab "Проблема и алгоритм голландского национального флага". Факультет информационных технологий (Клейтон), Университет Монаша, Австралия. 1998.
^ ab В главе своей книги «Дисциплина программирования» Прентис-Холл, 1976 г.
^ Последний случай происходит при сортировке строк с помощью быстрой сортировки по нескольким ключам . Ким, Ынсан; Пак, Кунсу (2009). «Улучшение быстрой сортировки по нескольким ключам для сортировки строк с множеством равных элементов». Information Processing Letters . 109 (9): 454–459. doi :10.1016/j.ipl.2009.01.007.
^ В этой статье использованы материалы, находящиеся в общественном достоянии, от Пола Э. Блэка. "Голландский национальный флаг". Словарь алгоритмов и структур данных . NIST .

Внешние ссылки

Объяснение и интерактивное пояснительное выполнение алгоритма, сортировка двух или трех цветов

[monash-1] "Проблема и алгоритм голландского национального флага". Факультет информационных технологий (Клейтон), Университет Монаша, Австралия. 1998.

[:0-2] В главе своей книги «Дисциплина программирования» Прентис-Холл, 1976 г.

[3] Последний случай происходит при сортировке строк с помощью быстрой сортировки по нескольким ключам . Ким, Ынсан; Пак, Кунсу (2009). «Улучшение быстрой сортировки по нескольким ключам для сортировки строк с множеством равных элементов». Information Processing Letters . 109 (9): 454–459. doi :10.1016/j.ipl.2009.01.007.

[NIST-4] В этой статье использованы материалы, находящиеся в общественном достоянии, от Пола Э. Блэка. "Голландский национальный флаг". Словарь алгоритмов и структур данных . NIST .