Проблема национального флага Нидерландов - Dutch national flag problem

Для статьи о голландском национальном флаге см. Флаг Нидерландов.
Голландский национальный флаг

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

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

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

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

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

Псевдокод

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

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

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

Рекомендации

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

внешняя ссылка