Блог

Главная - Вопросы по программированию - Инвариант цикла для раздела быстрой сортировки

Инвариант цикла для раздела быстрой сортировки

#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] происходит разделение.