분할에 대한 정확성 증명 정복 종류

Question

가정하자 우리가 정렬 방법 :

void DD_sort(int a[], int x, int y, int size_a) 
{ 
    if(x == y){ 
     return; 
    } 
    else if(y == x+1){ 
     if(a[x] > a[y]){ 
     /* swap the content */ 
     return; 
     } 
    } 
    else{ 
     int s = floor((y+1-x)/3); 
     DD_sort(a, x, y-s, s); 
     DD_sort(a, x+s, y, s); 
     DD_sort(a, x, y-s, s); 
    } 
} 

어떤 방법 우리는 정렬 알고리즘이 제대로 또는 잘못 배열을 정렬하는 것을 보여주기 위해 사용할 수 있습니까? 이 문제에 대한 체계적인 접근 방법이 있습니까? 나는 size_a == 1과 size_a == 2의 경우에 작동한다는 것을 이해한다. 그러나 size_a가 30이라고한다면, 우리는 ~ 2/3 크기의 배열을 반복적으로 호출하여 정렬 방법을 호출한다. 마치 작동하는 것처럼 보이지만 형식적으로 표시하는 방법을 모르겠습니다.

Answer 1

당신은이 라인

DD_sort(a, x, y-s, s); 
    DD_sort(a, x+s, y, s); 
    DD_sort(a, x, y-s, s); 

이 세 가지 통화의 각이 제대로 배열의 주어진 집합을 정렬합니다 주어진 X와 Y에서 전체 배열을 정렬합니다 것을 증명해야합니다. 마지막 세 번 호출은 x에서 y-s까지의 요소가 정렬되도록합니다. 두 번째 호출은 y-s에서 y로 요소가 정렬되도록합니다. 모든 요소가 정렬되었다고 결론을 내려면 y-s에서 y까지의 요소가 x에서 y-s까지의 요소보다 큼을 보여줘야합니다.

첫 번째 호출은 더 큰 s 요소가 y-s-s> = x + s 인덱스를 넘을 것을 보장하기 때문에 가능합니다. 따라서 두 번째 호출은 배열 끝으로 두 번째 호출을 보냅니다.

이 모든 추론은 배열의 길이가 정확히 3 * s이면 정확합니다. s가 길이의 3 분의 1보다 작 으면 true이고, 실제로 s가 작 으면 정렬 된 부분 집합이 더 큽니다.