быстрая сортировка инвариантных 3 условия с инвариантом цикла

Question

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

Основываясь на следующем алгоритме, я не понимаю свойств 1 и 2, приведенных ниже:

Вот алгоритм, на который я ссылаюсь:

Может кто-нибудь помочь мне разобраться в условиях

1) если $p \ leq k \leq i$ тогда $A[k] \leq x$

В алгоритме, когда, например,, $p$ является $1$, не будет $я$ быть $0$....Как это будет выполняться, поскольку перед циклом for у нас есть i = p-1

2) если $ i + 1 \leq k \ leq j - 1 $ тогда $A[k] > x$

В алгоритме, например, когда мы сначала вводим цикл for, и j = 1, то $я$ было бы равно 0....Я не понимаю, как это работает.

Спасибо

Answer 1

Если $p \ leq k \leq i$ тогда $A[k] \leq x.$ В алгоритме, когда, например,, $p$ является $1$, не будет $я$ быть $0$....Как это будет выполняться, поскольку перед циклом for у нас есть i = p-1

Хотя, как вы уже заметили, $я$ всегда меньше, чем $p$ в начале цикла он может стать больше, потому что оператор "$i=i+1$" в цикле может быть выполнено.Однажды $я$ был увеличен, по крайней мере, на $k=p$, у нас есть $p\le k\le i$.

Обратите внимание , что когда $p\le i$ не удерживается, т.е. когда нет $k$ такой , что $p\le k\le i$, условие "если $p \ leq k \leq i$ тогда $A[k] \leq x$" удерживается автоматически.(Напомним, что предложение "если false, то может произойти все, что угодно" всегда истинно.) Чтобы фальсифицировать это условие, мы должны найти пример $(p,k,i)$ такой , что $p \ leq k \leq i$ но $A[k]\gt x$.

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

Answer 2

Я не в настроении отслеживания кода, но понимаю, что вы начинаете с [r]= x и заканчиваются [i]= x

(Pivot, который, кажется, выбран в качестве последнего элемента $ R $ в данном коде, достигает его правильного положения со всей остальной частью списка.)

- На первый взгляд, может быть, код имеет некоторые ошибки, нет необходимости в обмене в затем скобках, а другой обмен должен ставки A [R] & A [J] внутри $ остальные $