divide_pivot 함수 pivoting algorithm

divide_pivot 함수 pivoting algorithm

이 divide_pivot 함수는 퀵소트의 개념을 응용하여 스택을 세 부분으로 나누는 역할을 합니다. 

피벗 설정:
c
p1 = stacks->max_size / 3;
p2 = (stacks->max_size / 3) * 2;
스택을 3등분하기 위해 두 개의 피벗(p1, p2)을 설정합니다.

 

반복 처리:
c
while (times < stacks->max_size)
스택의 모든 요소를 한 번씩 처리합니다.

 

요소 분류:
c
tmp = pop_top(stacks->stack_a);
if (tmp->val < p2)
{
    push_top(stacks->stack_a, tmp);
    pb(stacks);
    if (tmp->val < p1)
        rb(stacks);
}
else
{
    push_top(stacks->stack_a, tmp);
    ra(stacks);
}

 

스택 A의 top 요소를 확인합니다.
값이 p2보다 작으면:

 

스택 B로 이동(pb)
값이 p1보다 작으면 스택 B에서 회전(rb)

 

값이 p2 이상이면:
스택 A에서 회전(ra)

 

이 과정을 통해 스택은 다음과 같이 나뉩니다:
스택 A: p2 이상의 값들
스택 B의 상단: p1 이상 p2 미만의 값들
스택 B의 하단: p1 미만의 값들
이 분할 방식은 후속 정렬 과정을 더 효율적으로 만들어 줍니다.

 

이렇게 피봇팅 함으로써 스택 A에서는

큰 값이 보존되는데, p2 이상의 값들은 상대적으로 큰 값들입니다. 이들을 스택 A에 유지하면서 회전시키게 됩니다. 그리고 순환 검사를 하는데, 회전을 통해 스택 A의 모든 요소를 순차적으로 검사할 수 있습니다. 이는 while 루프가 max_size만큼 반복되는 동안 모든 요소를 한 번씩 확인할 수 있게 합니다. 그리고 균형 유지를 하게 되는데, 큰 값들을 스택 A의 하단으로 이동시켜, 스택의 균형을 유지합니다. 그리고 정렬 준비를 하게 되는데, 이 과정을 통해 p2 이상의 값들이 스택 A의 하단에 모이게 되어, 후속 정렬 작업을 위한 준비가 됩니다. 마지막으로 중복 처리 방지를 하는데 회전을 통해 이미 검사한 요소가 다시 top으로 오는 것을 방지합니다.
이러한 방식으로, 함수는 효율적으로 스택을 세 부분으로 나누면서 동시에 큰 값들을 스택 A에 유지하고 정렬을 위한 기초 작업을 수행합니다.