Разделение Hoare попадает в бесконечный цикл
Я пытаюсь написать функцию разбиения Hoare, которая принимает массив в качестве входных данных и разделяет его с первым элементом как pivot (я знаю, что это не очень хорошая идея, я должен использовать случайные pivots, как median-of-medians подход). Проблема в том, что эта функция попадает в бесконечный цикл, когда первый элемент самый высокий, как в случае с массивом [14,6,8,1,4,9,2,1,7,10,5], Я вижу ошибку, после первой итерации внешнего while, и то и другое i а также j равен 10, и, следовательно, цикл продолжается вечно. Какую часть я должен исправить, чтобы получить желаемый эффект? Вот код:
def hoare(arr):
pivot = arr[0]
i,j = 1,len(arr)-1
while i <= j:
while i < j and arr[i] < pivot:
i += 1
while j >= i and arr[j] >= pivot:
j -= 1
if i < j:
arr[i],arr[j] = arr[j],arr[i]
if j != 0:
arr[0],arr[j] = arr[j],arr[0]
return j
4 ответа
Я полагаю, что проблема заключается в том, что вы преобразовали цикл do-while (или повторение-пока, в терминах Хоара) в цикл while, поэтому он никогда не выполняет первый j -= 1.
Самым простым преобразованием в Python должно быть изменение двух внутренних циклов while следующим образом:
while True:
i += 1
if not (i < j and arr[i] < pivot): break
while True:
j -= 1
if not (j >= i and arr[j] >= pivot): break
(Я предполагаю, что if i < j: должен быть вне второго цикла while, а все остальные начальные отступы верны.)
Я не обосновал это полностью или не провел множество тестов, но, вероятно, в вашем переводе есть нечто большее, чем просто одна ошибка. Возможно, вам также понадобится преобразовать внешний цикл в do-while (на самом деле Hoare делает его явным while TRUE с проверкой в конце), но я не уверен. В любом случае, для вашего примера ввода измененная версия возвращает 9, а также arr является [10, 6, 8, 1, 4, 9, 2, 1, 7, 14, 5], что неверно, но решает проблему бесконечного цикла.
Следующая проблема - ошибка "один за другим". Если вы собираетесь сделать += 1 а также -= 1 сначала во внутренних циклах, вы должны начать с -1, len(arr) скорее, чем 0, len(arr)-1 (или, как вы сделали, 1, len(arr)-1).
Могут быть и другие проблемы. Но я не хочу копаться в вашем коде, находя все возможные ошибки и объясняя их. Если вам это нужно, расскажите нам, каков был наш источник, и объясните каждую трансформацию, которую вы сделали из этого источника, и вам будет намного легче объяснить, где вы ошиблись. Если нет, то гораздо проще просто перевести алгоритм Хоара на Python напрямую, и, надеюсь, вы сможете это выяснить.
Вот копия псевдокода Hoare, которую я нашел в Интернете (просто заменив все вкладки двумя пробелами):
Hoare-Partition (A, p, r)
x ← A[p]
i ← p − 1
j ← r + 1
while TRUE
repeat j ← j − 1
until A[j] ≤ x
repeat i ← i + 1
until A[i] ≥ x
if i < j
exchange A[i] ↔ A[j]
else
return j
Вот тривиальный перевод на Python; единственными изменениями являются второстепенный синтаксис (в том числе способ написания "exchange") и превращение каждого повторения / до некоторого времени в True/ перерыв.
def hoare(a, p, r):
x = a[p]
i, j = p-1, r+1
while True:
while True:
j -= 1
if a[j] <= x:
break
while True:
i += 1
if a[i] >= x:
break
if i < j:
a[i], a[j] = a[j], a[i]
else:
return j
Для функции с такой же подписью, как у вас:
def hoare0(arr):
return hoare(arr, 0, len(arr)-1)
В этой строке есть ошибка:
while i < j and arr[i] < pivot:
Должен быть:
while i <= j and arr[i] < pivot:
Весь код для раздела выглядит так:
def partition(a, l, r):
pivot = a[r]
i = l - 1
j = r
while i <= j:
if i <= j and a[i] < pivot:
i += 1
if i <= j and a[j] >= pivot:
j -= 1
if i < j:
a[i], a[j] = a[j], a[i]
a[l], a[j] = a[j], a[l]
return j
Почему возник бесконечный цикл?
В
pivot выбрано здесь 14.
Итак, после выполнения этого кода:
while i <j and arr[i] < pivot:
i += 1
i 10 и
j 10.
Теперь, когда этот блок выполняется:
while i <= j and arr[j] >= pivot:
j -= 1
В виде
a[10] < 14, Ничего не произошло. Поскольку,
i равно
j, свопа не происходит. Теперь, поскольку самый внешний цикл имеет условие
i <= j, цикл повторяется.
Что происходит с исправлением?
Итак, после выполнения этого кода:
while i <= j and arr[i] < pivot:
i += 1
i равно 11 (потому что условие все еще выполняется, когда
i равно
j) и
j 10.
Теперь, когда этот блок выполняется:
while i <= j and arr[j] >= pivot:
j -= 1
В виде
a[10] < 14, Ничего не произошло.
В настоящее время,
i 11 лет и
jравно 10, поэтому свопа не происходит. Но самый внешний цикл нарушен и
a[j] обменивается с
pivot.
Ваш массив становится:
[5, 6, 8, 1, 4, 9, 2, 1, 7, 10, 14]
Вы можете играть здесь. Он содержит код с отладочными отпечатками как для правильной, так и для неправильной схемы разделов.
Это также работает:
key = arr[0]
i = 0
j = n-1
while i >= j:
while arr[i] < key:
i += 1
while arr[j] > key:
j -= 1
arr[j], arr[0] = arr[0], arr[j]
Алгоритм разделения имеет много вариантов (короткий/длинный шаг), но мы должны быть очень осторожны с инвариантами, предварительными условиями и неструктурированными операторами программирования (break, return) в отношении этого классического алгоритма.
В противном случае мы можем попасть в большие неприятности. Даже если это может противоречить «питоновской» философии кодирования.
Следующее аннотированное решение (в дидактических целях) дает (10, [5, 6, 8, 1, 4, 9, 2, 1, 7, 10, 14]) для исходного списка [14,6,8,1,4,9,2,1,7,10,5], как и ожидалось. Комментарии можно убрать,
def hoare(arr):
# P: len(arr) > 0
assert len(arr)>0
i,j = 1,len(arr)
# INV : \forall n : 1<=n<i :arr[n]<arr[0]
# \forall n : j<=n<len(arr) :arr[n]>=arr[0]
# Quote(j-i)>=0
while i < j:
aa,bb=i,j
while aa < j and arr[aa] < arr[0]:
aa += 1
while bb > aa and arr[bb-1] >= arr[0]:
bb -= 1
#let
# aa = min n : i<=n<=j: n<j -> arr[n]>=arr[0]
# bb = max n : aa<=n<=j: n>aa -> arr[n-1]<arr[0]
#in
if (bb-aa)==(j-i):
#restore
arr[i],arr[j-1] = arr[j-1],arr[i]
#step
i, j = i+1 , j -1
else:
#restore
pass
#step
i,j = aa,bb
arr[0],arr[j-1] = arr[j-1],arr[0]
return j-1,arr
# Q : \forall n : 0<=n<j-1 :arr[n]<arr[j]
# \forall n : j-1<=n<len(arr) :arr[n]>=arr[j]
РЕДАКТИРОВАТЬ: я не против goto, breaks, and continue... Дональд Кнут подчеркивает, что "структурированное программирование" - это идея, а не язык... Как только вы поймете законы, вы сможете их нарушить... это больше питонический? Инвариант сохраняется, а цитата уменьшается в каждом цикле.
def hoare_non_str(arr):
assert len(arr)>0
i,j = 1,len(arr)
while i < j:
while i < j and arr[i] < arr[0]:
i += 1
if i==j:
break
while j > i and arr[j-1] >= arr[0]:
j -= 1
if i==j:
break
#It is safe to swap here.
arr[i],arr[j-1] = arr[j-1],arr[i]
i = i + 1
# swap pivote
arr[0],arr[j-1] = arr[j-1],arr[0]
return j-1,arr