네덜란드 국기 프로그램에 대한 이해

Question

Dutch national flag problem을 읽었지만 low 및 high 인수가 C++ 구현의 threeWayPartition 함수에 있는지 이해할 수 없었습니다.

나는 분하고 배열의 최대 요소로 가정하면

는 (data[i] < low) 및 (data[i] > high)는 항상 0을 반환하기 때문에 다음 if 및 else if 문은 의미가 없습니다, 정렬 할 수 있습니다.

어디서 잘못 되었나요?

Answer 1

low 및 high는 두 개의 값이 필요 당신이 세 방향의 파티션을 할 수있는 세 방향 파티션, 즉 할 정의 된 값입니다 파티션이 발생한 위치.단계별 예 :

data = [ 3, 1, 4, 9, 8, 2, 6, 9, 0 ] 
low = 4 
high = 8 

[ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ] 
p^ i^         q^ 

[ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ] 
    p^ i^        q^ 

[ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ] 
     p^ i^       q^ 

,274,286,838,332 10

[ 3 , 1 , 4 , 0 , 8 , 2 , 6 , 9 , 9 ] 
     p^  i^     q^ 

[ 3 , 1 , 0 , 4 , 8 , 2 , 6 , 9 , 9 ] 
      p^  i^    q^ 

[ 3 , 1 , 0 , 4 , 9 , 2 , 6 , 8 , 9 ] 
      p^  i^   q^ 

[ 3 , 1 , 0 , 4 , 6 , 2 , 9 , 8 , 9 ] 
      p^  i^  q^ 

01,235 16,

[ 3 , 1 , 0 , 4 , 6 , 2 , 9 , 8 , 9 ] 
      p^   i^ q^ 

[ 3 , 1 , 0 , 2 , 6 , 4 , 9 , 8 , 9 ] 
       p^   iq^ 

알고리즘은 당신이 말하기를 : 요소 바닥 위의

• 스왑 (즉, p + 1) 바닥 아래 모든 것이 이미 확인 되었기 때문에, 또는
• 스왑 맨 위의 모든 것이 이미 확인 되었기 때문에 요소 즉 상단 (q - 1 이하)이나
• 는를 남겨 중간에 속하기 때문에 요소입니다.

당신은 각각 하단, 중간 및 상위 파티션 등 [3, 1, 0, 2], [6, 4] 및 [9, 8, 9]를 얻을.

Answer 2

} else if (data[i] >= high) {은 기사에 쓰여진 내용이 아닐 수도 있음을 보여줍니다.

Answer 3

중간 파티션의 값에 대해 low 및 high을 반 개방 범위 [low,high)으로 생각하십시오. low보다 작은 모든 값은 왼쪽 분할로 끝납니다. 중간 파티션에는 low부터 최대 high까지의 값이 포함됩니다. 마지막으로 high 이상의 모든 값은 올바른 파티션으로 끝납니다. 당신이 이동 무엇 C++ 프로그램에서

[bottom] <= low < [middle] < high <= [top] 

: