Разница между голландским флагом pr0blem и сортировкой

Question

Я читаю Dutch national flag problem, и я не понимаю: почему это отличается от простой проблемы сортировки?

Я имею в виду: если мы назначаем 0 красному цвету, от 1 до белого и от 2 до синего, а также выполнить стандартную мерную сортировку или что-то еще ... почему я не могу получить правильный ответ?

Я что-то упустил?

Answer 1

Проблема голландского национального флага - это особый случай более общей проблемы сортировки, где единственными допустимыми элементами являются 0, 1 и 2. Вы можете абсолютно решить это, используя стандартный алгоритм сортировки.

Проблема сама по себе частично интересна по историческим причинам, но в значительной степени потому, что сложно найти решения, стабильные, эффективные по времени (O (n)) и эффективные по площади (O (1)). Легко получить решения с двумя из этих трех свойств, но получение всех трех (я считаю) открытая проблема. Это также интересно как место для разработки алгоритмов быстрого сортировки и разбиения на дубликаты ключей; вы можете думать, что 0, 1 и 2 меньше, чем ось вращения, равная оси вращения, и больше, чем ось поворота, и вы в основном имеете быструю сортировку с повторяющимися элементами.

Надеюсь, это поможет!

Answer 2

В этой задаче диапазон значений элементов для сортировки мал. В таких случаях для сортировки массива можно использовать сортировку без сравнения (например, сортировку). Алгоритмы сортировки сортировки могут сортироваться в O (n), что быстрее, чем обычные алгоритмы сортировки сравнения, такие как quicksort.