축값이 중간에 있을 경우의 partition

int partition(dataType *a[],int begin, int end) {
    int pivot=(begin+end)/2;
    int i=begin, j=begin;  // 범위는 begin 에서 end 까지 이며 end도 포함된다.
    int val;
    dataType *temp;

    // swap a[pivot] and a[end]
    // to locate pivot value at the end of the list
    temp=a[pivot];
    a[pivot]=a[end];
    a[end]=temp; 

    val=temp->total;

    for(i=begin;i<end;i+=1) {
        if(a[i]->total<=val) {
            if(j<i) {
                temp=a[j];
                a[j]=a[i];
                a[i]=temp;

            }

            j+=1;
        }
    }
    temp=a[j];
    a[j]=a[end];
    a[end]=temp;
    return j;
}

 

// 내림차순으로 바꾸어 줄려면 아래와 같이 바꾸어 주면 됩니다.
if(a[i]->total>=val) {
 
위의 파티션 알고리즘은 새버젼으로 간단하고 효과적입니다.
새버젼은 리스트를 세부분[혹은 네부분]으로 나누어서 생각하는 것입니다
 
[축값보다 같거나 작은 부분][축값보다 큰 부분 :: 시작위치 j][아직 모르는 부분 :: 시작위치 i][축값]
처음에는 축값보다 같거나 작은 부분은 없습니다. 축값보다 큰 부분도 없습니다.
 
하지만 맨처음의 위치 [begin]을 축값보다 큰 부분의 시작위치 j 로 잡아도 문제가 생기지 않습니다.
코드를 잘 연구해 보면 알수 있습니다.
 
만약 i의 위치에 있는 값이 축값보다 같거나 작댜면 축값보다 큰 값이 j의 위치에 있는 것과
서로 바꾸어 주면 [작은부분][큰부분][모르는부분][축값]이 유지될 수 있습니다.
 
물론 작은 부분은 크기가 1 증가 합니다. 큰 부분은 오른쪽으로 한칸 이동 합니다.
모르는 부분도 자동적으로 한칸 오른쪽으로 이동합니다.
 
만약 i의 위치에 있는 값이 축값보다 크다면 [작은부분]은 그대로 이고 [큰부분]은 크기가
하나 늘어 납니다. 큰부분의 시작위치는 바뀌지 않고 모르는 부분은 한칸 오른쪽으로 이동합니다.
 
끝까지가서 어떻게 처리해야 할지도 코드를 잘 연구해보면 알수 있습니다.