#algorithm #sorting #quicksort #loop-invariant
#алгоритм #сортировка #быстрая сортировка #инвариант цикла
Вопрос:
У меня возникли проблемы с определением и доказательством инвариантности цикла для некоторой реализации алгоритма быстрой сортировки. Это не версия раздела Ломуто или Хоара.
Если вы знаете о какой-либо известной версии быстрой сортировки, которая реализована таким образом, дайте мне знать, пожалуйста.
Реализация алгоритма на Python:
def partition(arr: list, p: int, r: int):
y = arr[p]
i = p
j = r 1
while i < j:
i = i 1
while i <= r and A[i] < y:
i = i 1
j = j - 1
while j >= p and A[j] > y:
j = j - 1
if i <= j:
swap(arr, i, j)
swap(arr, j, p)
return j
def quicksort(arr: list, p: int, r: int):
if p < r:
q = partition(arr, p, r)
quicksort(arr, p, q - 1)
quicksort(arr, q 1, r)
def swap(arr: list, i, j):
tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
Мне удалось определить следующий инвариант цикла (это может быть неверно):
В начале каждой итерации
while
цикла для каждого индексаk
в массивеA
:
если
k = p
, значитA[k] = y
если
p < k <= i
, значитA[k] < y
если
j <= k <= r
, значитA[k] > y
Пожалуйста, помогите мне определить инвариант цикла для while
цикла в partition()
методе (если приведенное выше неверно) и докажите это.
Комментарии:
1. это разновидность быстрой сортировки, известная как разбиение под голландским флагом, она используется, когда массив состоит в основном из дубликатов. вместо перемещения одного итератора вперед, вы перемещаете два итератора от начала и конца друг к другу. они останавливаются всякий раз, когда указывают на одно и то же значение (т. Е. pivot)
2. @mangusta Я читал о разделении под голландским флагом, но это кажется немного другим. В моем случае элемент pivot является первым (
y = arr[p]
).3. любой элемент массива может быть стержнем
4. @mangusta: на самом деле, любое значение может быть сводным, при условии, что массив содержит по крайней мере один элемент не большего размера и один не меньший. Например, среднее значение могло бы сделать.
Ответ №1:
Инвариант внешнего while выражает, что среди разделов массива, которые были отсканированы до настоящего времени, а именно диапазонов A[p..i]
и A[j..r]
, левые элементы не больше, чем pivot, а правые элементы не меньше. (И, конечно, содержимое A является перестановкой исходного содержимого.)
При завершении цикла все левые элементы не больше всех правых элементов, так что A[p..r]
происходит разделение.