QuickSort 불변의 3 조건 루프 불변의 조건

Question

Quicksort를 공부하는 QuickSort, Leiserson, Rivest 및 Stein이 "알고리즘에 대한 소개"를 사용하여 정확성을 보여주기 위해서는 불변성이 루프의 3 단계, 초기화, 유지 보수 및 해지를 유지해야합니다. 루프의.

다음 알고리즘을 기반으로, 아래의 속성을 이해하지 못합니다.

여기를 참조하는 알고리즘입니다.

>

누군가가 조건을 이해하는 데 도움이 될 수 있습니다

1) $ P \ LEQ K \ LEQ i $ 그런 다음 $ a [k] \ leq x $ < / span>

예를 들어 $ p $ 은 $ 1 $ 입니다. class="수학 용기"> $ i $ 수학 - 용기 "> $ 0 $ ....이 루프 앞에 우리는 i = p-1를 가지고 있기 때문에 < / P>

2) $ i + 1 \ Leq K \ Leq J - 1 $ $ a [k]> x $

예를 들어 알고리즘의 루프 및 J= 1을 입력하면 $ i $ 은 0이 될 것입니다. t 이것은 어떻게 작동 하는지를 확인합니다.

감사합니다

Answer 1

$ p \ leq k \ Leq i $ 다음 $ a [k] \ leq x. $ 예를 들어 $ P $ 은 $ 1 $ 입니다. $ i $ $ 0 $ ....이 루프 앞에 우리는 i = p-1

가 있기 때문에

, $ i $ 은 항상 $ p $ 보다 작습니다. 루프의 시작, " $ i= i + 1 $ "명령문이 실행될 수 있기 때문에 더 커질 수 있습니다. 적어도 $ k= p $ 에 대해 $ i $ 이 증가했습니다.="수학 용기"> $ P \ LE K \ LE i $

$ p \ le i $ 은 $ k $ < / span> $ p \ le k \ le i $ , $ p \ leq k \ leq i $ 그런 다음 $ a [k] \ leq x $ "이 자동으로 보관됩니다. (예상 제안은 "거짓이면 어떤 일이 일어날 수 있습니다"라고 회상합니다.) 항상 그 상태를 위조하기 위해 $ (P, K, I) $의 인스턴스를 찾아야합니다. $ p \ Leq K \ Leq i $ 그러나 $ a [k] \ gt x $ < / span>.

지금 두 번째 루프 불변의 경우를 알아낼 수 있어야합니다.

Answer 2

나는 코드를 추적하는 기분이 아니지만, u가 [r]= x로 시작하고 [i]= x

로 끝납니다.

(주어진 코드에서 마지막 요소 $ R $ 로 선택한 것처럼 보이는 피벗은 나머지 목록과 함께 올바른 위치에 도달합니다.)

-AT 첫눈에 코드가 몇 가지 오류가 있고, 그때 괄호 안에서 교환이 필요하지 않으며 다른 교환은 $ else $