Проблема с национальным флагом Нидерландов, запущенная в O (n)

Question

Я учусь в 10-м классе на CompSci 1. В нашем учебнике, Практическое программирование, 3-е издание, Введение в информатику с использованием Python 3.6 , упоминается проблема голландского национального флага.Ниже приводится слово «слово в слово» к упражнению:

Эдсгар Дейкстра известен своей работой над языками программирования.У него возникла изящная проблема, которую он назвал проблемой голландского национального флага: дан список строк, каждая из которых является «красной», «зеленой» или «синей» (каждая представлена ​​несколько раз в списке),измените список так, чтобы строки были в порядке голландского национального флага - сначала все «красные» строки, затем все «зеленые» строки, затем все «синие» строки.

Вот код Python, который я написал для упражнения:

def dutch_flag(colors: list)-> list:
  """
  This function takes a list of strings of colors (red, green, 
  or blue),and returns a list containing them with the reds first, 
  the greens second, and the blues last.
  """
  reds = 0
  greens = 0
  blues = 0
  for color in colors:
    color = color.lower().strip()
    if color == "red":
      reds += 1
    elif color == "green":
      greens += 1
    elif color == "blue":
      blues += 1

  flag = []
  for i in range(0, reds):
    flag.append("red")
  for i in range(0, greens):
    flag.append("green")
  for i in range(0, blues):
    flag.append("blue")

  return flag  

Мой код выполняется за O (n) времени.Однако мой учитель сказал нам, что для этой программы требуется алгоритм сортировки, который в лучшем случае равен O (n * logn).Почему мой код быстрее?

Answer 1

То, что вы показываете, является сортировкой подсчета. Другими вариантами, не относящимися к сравнению, были бы сортировка по сегментам или сегментам, которые также имеют O (n) временную сложность.

Эту проблему также можно решить с помощью функции 3-стороннего разбиения, основанной на сравнении, которая использует сравнения и свопы с временной сложностью O (n).

https://en.wikipedia.org/wiki/Dutch_national_flag_problem#Pseudocode

Обычно сортировки на основе сравнения занимают время O (n log (n)), но проблема с национальным флагом Нидерландов не требует этого.

Функция трехстороннего разделения может быть расширена для обработки большего количества цветов. Первый проход разделяет массив на 3 вложенных массива: маленький, средний и большой, затем повторяет процесс для каждого вложенного массива, разделяя его на 3 вспомогательных массива и так далее. За 2 прохода можно выполнить 9 цветов, 1-й проход разделяется на маленький, средний, большой, а 2-й проход разделяет каждый суб-массив на 3 части, что также является O (n) временной сложностью. Для n элементов и k цветов временная сложность равна O (n⌈log3 (k) ⌉), но, поскольку k является постоянной, временная сложность составляет O (n).