Бесконечность как страж в слиянии?

Question

В настоящее время я читаю «Введение в алгоритмы» Кормена и обнаружил нечто, называемое часовым.

Используется в алгоритме сортировки слиянием в качестве инструмента для определения, когда один из двух списков слияния исчерпан.Кормен использует символ бесконечности для часовых в своем псевдокоде, и я хотел бы знать, как такое бесконечное значение может быть реализовано в C.

Answer 1

Часовой это просто фиктивное значение. Для строк вы можете использовать NULL-указатель, поскольку в списке это не очень разумно. Для целых чисел вы можете использовать значение, которое вряд ли встречается в вашем наборе данных, например если вы имеете дело со списком возрастов, то вы можете использовать возраст -1 для обозначения списка.

Answer 2

Если вы знаете, что элементы в вашем списке будут варьироваться от наименьшего до максимально возможного значения для данного типа данных, код, который вы просматриваете, не будет работать.Вам придется придумать что-то еще, что, я уверен, можно сделать.Прямо сейчас у меня есть эта книга, и я смотрю на код, который вызывает у вас проблемы, и у меня есть решение, которое будет работать для вас, если вы знаете, что значения варьируются от наименьшего для данного типа данных до наибольшего минусаодин максимум.Откройте эту книгу обратно на страницу 31 и посмотрите на функцию слияния.Строки, вызывающие у вас проблемы, это строки 8 и 9, в которых используется дозорное значение бесконечности.Теперь мы знаем, что два массива уже отсортированы, и нам просто нужно объединить их, чтобы получить массив, который в два раза больше и в отсортированном порядке.Это означает, что самые большие элементы в каждой половине находятся в конце подмассивов, и что самый большой из двух элементов является самым большим в массиве, который в два раза больше, и мы будем сортировать после завершения функции слияния.Все, что нам нужно сделать, это определить наибольшее из этих двух значений, увеличить это значение на единицу и использовать его в качестве нашего стража.Итак, строки 8 и 9 кода должны быть заменены следующими 6 строками кода:

if L[n1] < R[n2]
  largest = R[n2]
else
  largest = L[n1]

L[n1 + 1] = largest + 1
R[n2 + 1] = largest + 1

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

Answer 3

в C, при сортировке массива вы обычно знаете размер, чтобы вы могли на самом деле отсортировать диапазон [begin, end), в котором end - один за концом массива.Например, int a[n] может быть отсортировано как sort(a, a + n).

. Это позволяет вам делать две вещи:

• рекурсивно вызывать вашу сортировку с частью массива, которую вы не сортировалипока (сортировка слиянием является рекурсивным алгоритмом)
• используйте end в качестве стража.

Answer 4

Вы можете получить «бесконечное значение» для чисел с плавающей точкой, но это не лучшая идея.Для массивов передайте размер явно;для списков используйте нулевой указатель часового.

Answer 5

Хитрость в том, что вам не нужно проверять границы массива при увеличении индекса только в одном из списков во внутреннем цикле while. Следовательно, вам нужны часовые, которые больше всех других элементов. В с ++ я обычно использую std::numeric_limits<TYPE>::max().

С-эквивалент должен быть макросом типа INT_MAX, UINT_MAX, LONG_MAX и т. Д. Это хорошие стражи. Если вам нужны два разных стража, используйте ..._MAX и ..._MAX - 1

Все это предполагает, что вы объединяете два списка, которые упорядочены по возрастанию.