Голландских национальный флаг - Выведение решения

Question

После изучения элементарных видов, выбора рода, сортировки вставки & куча сортировка из Седжвик course в Coursera.

Выбор сортировки - окончательный порядок сортировки начинает формировать каждую итерацию

Вставка сортировки - порядке возрастания (не окончательный) начинается формирование каждой итерации.

Куча сортировка - Агрессивная версия вставки сортировки.

---

У меня есть задание, в указанном выше курса, после изучения алгоритмов сортировки (как показано выше),

голландский национальный флаг. Учитывая массив из n ведер, каждый из которых содержит красный, белый или синий галька, сортируйте их по цвету. Допустимые операции:

swap(i,j): swap камешек в ведро i с галькой в ​​ведре j.

color(i): цвет гальки в ковше i.

Требования к производительности заключаются в следующем:

В наиболее n звонки на color().

Не более n Звонок swap().

Постоянное дополнительное пространство.

---

Читая этот вопрос,

От требований к производительности, учитывая, я получить подсказку, что n свопы требуются (по-большей части). Из этого намека, я думаю,

1) Вставка сортировки, которая обеспечивает n свопов для n инверсионных пар.

2) Принимая цвета, которые хранятся в ведрах, существует очень большая вероятность того, что подобные цвета подойдут ближе, учитывая n ковшей. Это приводит к ситуации частично отсортированного массива, где массив частично сортируется, если число инверсий < = cn.

Исходя из этих двух вышеупомянутых выводов,

Вопрос:

1)

ли мыслительный процесс правильно выводя для вставки рода, как решение?

2)

Что такое хэш-функция хэш цвета и вставки цвета в качестве частично отсортированного массива? Нужен ли мне метод линейного зондирования?

3) Зачем нам нужно дополнительное пространство, как указано в вопросе? Поскольку Вставка сортировки в месте алгоритма

Примечание: Для того, чтобы подтвердить свой мыслительный процесс, прежде чем писать код

Answer 1

Чтобы разработать решение этой проблемы, вам не нужны указанные алгоритмы.

Вместо этого ознакомьтесь с реализацией подпрограмм Быстрого Сорта - это действительно поможет.

P.S.

Heap рода - Агрессивная версия вставки рода

Нет, вы не правы, это совершенно другой подход

Вы можете рассмотреть, как Шелл это использовать Вставку рода внутренне

Answer 2

Я не думаю, что вам следует (или нужно) предположить, что более близкие ведра имеют более высокий шанс иметь один и тот же цвет. Проблему можно решить, сохраняя индексы первого появления двух из трех цветов (которые не считаются «первыми» в упорядочении). Замена цвета со значениями 0, 1, 2, я считаю, этот код удовлетворяет требованиям:

public class Z { 
    private static int first1, first2; 

    private static void swap(int[] v, int i, int j) { 
    int tmp = v[i]; 
    v[i] = v[j]; 
    v[j] = tmp; 
    } 

    private static void sort(int[] v) { 
    first1 = -1; 
    first2 = -1; 
    for(int i=0; i<v.length; i++) { 
     switch(v[i]) { 
     case 0: 
      if (first1 != -1) { 
      swap(v, i, first1); 
      if (first2 != -1) { 
       swap(v, i, first2); 
       first2++; 
      } 
      first1++; 
      } else if (first2 != -1) { 
      swap(v, i, first2); 
      first2++; 
      } 
      break; 
     case 1: 
      if (first2 != -1) { 
      swap(v, i, first2); 
      if (first1 == -1) { 
       first1 = first2; 
      } 
      first2++; 
      } else if (first1 == -1) { 
      first1 = i; 
      } 
      break; 
     case 2: 
      if (first2 == -1) { 
      first2 = i; 
      } 
      break; 
     } 
    } 
    } 
    public static String toString(int[] v) { 
    StringBuilder sb = new StringBuilder(); 
    sb.append("["); 
    for(int i=0; i<v.length; i++) { 
     sb.append(v[i]); 
     sb.append(" "); 
    } 
    sb.append("]"); 
    return sb.toString(); 
    } 

    public static void main(String[] args) { 
    int c = Integer.parseInt(args[0]); 
    int[] v = new int[c]; 
    while(true) { 
     int[] tmp = v.clone(); 
     System.out.print(toString(tmp) + "=>"); 
     sort(tmp); 
     System.out.println(toString(tmp)); 
     int prev = -1; 
     for(int j=0; j<tmp.length; j++) { 
     if (tmp[j] < prev) { 
      throw new Error(); 
     } 
     } 
     int j; 
     for(j=0; j<c; j++) { 
     v[j]++; 
     if (v[j] == 3) { 
      v[j] = 0; 
     } else { 
      break; 
     } 
     } 
     if (j == c) { 
     break; 
     } 
    } 
    } 
} 

Answer 3

На первый взгляд это выглядит как введение в ведро рода: двигаться каждый красный камушек в массив Reds, перемещать каждую белую гальку в Whites array, переместите все синие гальки в массив Blues, а затем скопируйте эти 3 массива в конечный выходной массив. Наивная реализация займет 3 * п вызовы цвета(), 2 * п вызовы свопа() и п + постоянной дополнительной памяти.

Но ограничения немного отличаются от ограничений ... Мы не можем позволить себе простые решения, мы не можем позволить себе дополнительную память для временных массивов.

Отметьте, что n - это длина входного массива, а не количество перестановок и не умноженная на что-то. То есть:

• каждый вызов свопа() должны поместить один камешек в его окончательном месте
• свопов должны быть сделаны на месте
• каждый вызов цвета() должен привести к необходимости звонок swap()

Это возможно в случае только трех цветов.Для того, чтобы сделать возможным, мы можем разделить входной массив 3 (4) секций:

г) красной галькой в ​​начале массива

ш) белые камешки следуют красные камешки с самого начала

U) необработанный галька следует белым камешкам до голубых камешков

б) синих камешков в конце массива

Давайте предположим, что мы используем 0 на основе индексации массивов. Итак, index a [0] - это первый элемент массива, а [n-1] - последний элемент массива.

Теперь, чтобы отслеживать состояние массива можно использовать несколько переменные:

• переменного г будет держать количество обработанных красных камешков

• переменных ж будет держать количество обработанной белой гальки

• переменная b будет содержать количество обработанной голубой гальки

• переменная i will ho ld Текущий индекс гальки для обработки (обработан)

Это может быть инвариантно для обработки цикла. При запуске r = 0, w = 0, b = 0, i = 0. На конце r, w, b удерживайте число соответствующих гальки и i = n-b.

Таким образом, массив будет выглядеть в самом начале:

 
uuuuuuuuuuuu 
^   ^
r   n=n-0=n-b 

массив будет выглядеть следующим образом во время обработки:

 
rrwwwuuuuuuub 
^^ ^
    r w+r n-b 
    i 

Arrya будет выглядеть в конце:

 
rrrwwwwwwbbbb 
^^ ^^
0 r  n-b n 
     w+r 
     i 

Каждый шаг обработки цикла (i увеличивается после этого), мы принимаем решение и делаем одну из трех возможных вещей s:

• если [я] красный, мы делаем своп (г, г) и увеличить R
• если [я] белый, мы увеличиваем вес - это бесполезное действие, на самом деле, как мы на самом деле не используют w, но я думаю, что лучше сделать это для выполнения
• , если [i] синее, мы увеличиваем b и делаем swap (i, nb) - мы можем пропустить свопы, если i = nb, но в целом алгоритм должен работать без этого пропустить

Loop заканчивается один раз я> = пь

Теперь на ваши вопросы:

Правильно ли этот процесс выдумывания при вводе сортировки в качестве решения?

Неа, сортировка вставкой будет делать больше, чем п вызовы цвета() и более п вызовы свопа()

Что такое хэш-функция для хеширования цвета и цвета вставки в виде частично отсортированного массива?

Вы не указали порядок цветов, поэтому я решил это сам. Но вам не нужен хэш для гальки, так как он увеличит количество свопов, если вы поместите гальку во временную структуру данных.

Нужен ли мне метод линейного зондирования?

Это сложная часть - один вызов цвета() на вход галька (не более 1). Вы можете сохранить результат color() в локальной переменной, а затем использовать локальную переменную в, например, операторе case. Строго сказано, что это неправильно - вы все еще делаете больше сравнений цвета, чем нужно, но, вероятно, ваш учитель согласится с этим подходом, поскольку вы все еще вызываете color() только такое количество раз. На самом деле Хэш не нужен.

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

Поскольку вы не указали PL и как представлены цвета, трудно предположить, как это можно сделать эффективно.

Зачем нам нужно дополнительное пространство, как указано в вопросе? Поскольку сортировка Insertion является алгоритмом на месте

Даже сортировка вставки использует дополнительное пространство для локальных переменных.

P.S. Я не пишу готовый к использованию код, так как это ваш приказ. Не стесняйтесь обновлять ответ своим кодом, если что-то пойдет не так, когда вы его реализуете в коде.

Answer 4

1) Сортировка вставки, которая обеспечивает n свопов для n инверсионных пар.

2) Принимая цвета, которые хранятся в ведрах, существует очень большая вероятность того, что подобные цвета подходят ближе, учитывая n ковшей. Это приводит к ситуации частично отсортированного массива, где массив частично сортируется, если число инверсий < = cn.

Есть две проблемы с этой линией рассуждений.

Первое, что число инверсий не O (n) в худшем случае. Чтобы понять, почему, представьте, что у вас есть ^н/ синие камешки с последующим ^п/ красных камешков (и без белых камешков).Затем общее число обращений составляет ⁽ⁿ⁾/. (И, кроме того, судя по некоторым быстрых экспериментов я просто запустить, даже в среднем случае общее число инверсий ^(п)/ - до сих пор не O (п).)

Вторая проблема с этой линии рассуждений является то, что вы просили, чтобы ограничить число свопов точно п, а не O (п). Так что даже если сортировка вставки требуется только (скажем) 2 & # xFEFF; n свопов, которых все равно было бы слишком много.

---

2) [¶] Что такое хэш-функция хэш цвета и вставить цвета в качестве частично отсортированного массива? Нужен ли мне метод линейного зондирования?

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

Скорее, вы можете просто представить три цвета, как (скажем) 0, 1 и 2.

3) Почему нам нужно дополнительное пространство, как указано в вопросе? Поскольку сортировка вставки является алгоритмом на месте

Даже для сортировки вставки требуются дополнительные переменные, например массивные индексы.

---

Александр Аникин уже предложил такое же решение, что я собирался предложить, но я не уверен, если это ясно из его ответа, как вы могли бы придумать что по своему усмотрению, так что остальная часть этого ответ проведет вас через это.

---

Итак, предположим, вы начинаете с попытки вставки сортировки. Затем мы можем улучшить его постепенно, пока он не удовлетворит требования. (Это требует наличия нескольких идей, но каждое индивидуальное улучшение требует лишь небольшого понимания, а не для решения всей проблемы сразу.)

Первое улучшение: # звонков color(i).

Когда мы хотим вставить новый галькой в ​​уже отсортированную часть массива, нам нужно найти, куда он должен идти в этой части.

С чистой сортировкой вставки мы делаем это, исследуя гальки в уже отсортированной части массива. Но нам разрешено только звонить colorn раз; и мы ожидаем, что будем называть его по крайней мере один раз для каждого камешка - вы не можете сортировать камешек, не изучая его - это означает, что для выполнения этой работы нам нужно называть его ровно один раз для каждого гальки. Мы не можем позволить себе повторно вызвать его для гальки, которую мы уже отсортировали.

Чтобы исправить это, ключевое понимание состоит в том, что в уже отсортированной части массива нам действительно не нужно проверять ведро, чтобы узнать, какой цвет он имеет, если мы отслеживаем сколько гальки мы уже видели в каждом цвете. Если мы ранее видели r красные камешки, w белых камешков и b голубых камешков, а затем красные камешки в ведре 0 через r-1, белые из них находятся в r через r+w-1 и синие в ведре r+w через r+w+b-1. Таким образом, мы можем выяснить, где вставить новый камешек, не называя фактически color на любые другие гальки.

Второе усовершенствование: # звонков swap(i,j), часть 1.

Следующая проблема заключается в том, что с чисто сортировки вставками, вставка галечные означает «смещение» все камешки после него, что потенциально означает большое количество свопов. (Например, если мы уже видели 10 белых гальки и 5 голубых гальков, то вставка красной гальки означает «сдвиг» 15 гальки, что требует 15 своп.)

Чтобы исправить это, ключевым понятием является то, что мы на самом деле не заботятся о порядке гальки внутри цветовой группы; красная галька может прийти в любом порядке, за ней следуют белые гальки в любом порядке, за которыми следуют голубые гальки в любом порядке. Таким образом, вместо того, чтобы переместить большое количество гальки только на одну позицию, мы можем перенести одну гальку с начала цветовой группы до ее конца.

Например, если мы ранее видели r красные камешки, w белых камешков и b голубых камешков, и нам нужны вставить новый красный камушек, то мы можем поменять его в положение r (что дает нам белый камешек (если w > 0)), затем поменяйте белый галькой в ​​положение r+w (давая нам синий камешек (если b > 0)).

Это подводит нас к O (п) обменивает в худшем случае, и как раз под n свопами в среднем случае: красная галька потребует два свопов (если w > 0 и b > 0), белая гальки потребует один обмен (если b > 0), а синий галька потребует нулевых свопов.

Третье улучшение: # звонков swap(i,j), часть 2.

Но это по-прежнему оставляет нас с потенциально слишком много свопов: если есть более красные камешки, чем синие, то мы будем (обычно) заканчиваются более чем n свопы.

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

Так, например, если мы уже видели r красные камешки, w белых камешков и b голубых камешков, а затем красные камешки должны быть в позиции 0 через r-1, белые камешки должны быть в позиции r через r+w-1, и голубые гальки должны находиться в положениях n-b по n-1. Положения от r+w до n-b-1 являются пока еще несортированными.

---

Таким образом, наш окончательный алгоритм выглядит следующим образом:

• инициализации r, w и b к 0.
• Инициализировать i до 0.
• в то время как i < n - b:
  • проверка color(i):
    • если это красный, то swap(i, r) и приращение r и i.
    • если это WHITE, то просто увеличивайте w и i.
    • если это ГОЛУБОЙ, то swap(i, n-b-1) и приращение b. Do не приращение i (потому что галька в позиции i - это та, которую мы только что вытащили из конца массива, которую мы еще не изучили).

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

---

Теперь, если бы мы начали с другого вида, а не вставки сортировки? Некоторые виды по-прежнему ведут нас в правильном направлении; например, если мы начали с сортировки в виде ведра (или рода сортировки радикса только с одной цифрой 0-2), мы все равно могли бы сделать инкрементные исправления, чтобы они закончили описанный выше алгоритм. Другие виды сортов не так хорошо выработали бы, но все же могли бы привести к полезной информации, которая помогла бы, когда мы перейдем к лучшему пути. Поэтому важно попробовать разные вещи и сохранить открытость. Чем больше вы исследуете проблему, тем больше информации вы получаете, даже если вы иногда спускаетесь по неправильному пути и должны отступать и попробовать что-то новое.

Answer 5

Как намек, Wikipedia говорит следующее, курсив мой:

Голландская национальная проблема флаг является проблемой информатики программирования, предложенный Эдсгер Дейкстры. Флаг Нидерландов состоит из трех цветов: красного, белого и синего. Учитывая шары этих трех цветов, расположенных случайным образом в строке (фактическое количество шаров не имеет значения), задача состоит в том, чтобы расположить их так, чтобы все шары одного цвета были вместе, а их коллективные группы цветов находятся в правильном порядке.

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

(Для решения, the article also has pseudocode для алгоритма)