Назначение контрольных значений в сортировке merge

Question

В настоящее время я беру свой первый класс алгоритмов, и мы недавно начали говорить о сортировке слияния. Наш профессор показал нам псевдокод для сортировки счисления с дозорными значениями, но на самом деле не объяснил их цели. Я все еще довольно смущен в отношении того, для какой цели они служат, поскольку одной из наших проблем с домашним заданием является запись сортировки слияния без дозорных значений. Существуют ли какие-либо преимущества или недостатки для включения в себя дозорных значений? Любая помощь будет принята с благодарностью.

Редактировать: Как примечание, я запрограммировал сортировку слиянием ранее и сделал это без значений дозорных, что является частью того, что привело к моей путанице.

Answer 1

Значения Sentinel просто делают это так, что вы можете выполнить слияние в 1 для цикла, а не 3 для циклов. Любые различия в производительности или памяти крошечные, и оба метода совершенно верны; используйте то, что вы предпочитаете.

Answer 2

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

Например:

Я опишу это как это описано во введении и анализе алгоритмов с помощью Cormen, Leiserson, Ривеста и Stein, с использованием двух стопок игральных карт, чтобы представить два массива для сортировки.

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

Назовем левую кучу карточного массива «L» и правую груду карточного массива «R».

Для каждой итерации сортировки слияния мы сравним верхнюю карту на каждой куче и определим, какая из них самая маленькая. Мы возьмем самую маленькую карту из кучи и поместим ее лицом вниз, чтобы создать новую кучу сортированных карточек. Это всеобъемлющий принцип сортировки слияний.

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

Использование дозорного устройства не позволяет нам выполнять эту дополнительную проверку перед каждым сравнением, гарантируя, что мы никогда не сможем удалить все карты из одной или другой сваи. Если бы мы использовали «бесконечность» как ценностное значение, то карта «бесконечности» НИКОГДА не будет удалена из кучи, потому что значение никогда не будет больше, чем «бесконечность». Это гарантирует, что ВСЕГДА будет значением в массиве для сравнения.

Подумайте об этом примере: где карты в левой куче последовательно меньше, чем карты в правой куче. Карты в левой куче будут удалены по одному, пока не будет достигнута карта «бесконечности» (дозорной). Затем карты в правой куче начнут истощаться.

В какой-то момент у СВОЙ свай будет карта «бесконечность» сверху.Однако к этому моменту счетчик циклов достигнет максимального значения, в результате чего цикл завершится до того, как он попытается получить доступ к индексу массива, который не существует.