피봇을 사용한 스택 정렬 알고리즘 | Stack sorting algorithm using pivots

피봇을 사용한 스택 정렬 알고리즘 ❘ Stack sorting algorithm using pivots

이 코드는 스택 정렬 알고리즘의 일부로 , 피벗을 사용하여 스택을 세 부분으로 나누는 함수입니다. 

함수 개요
void divide_pivot(t_var *stacks)

이 함수는 t_var 구조체 포인터인 stacks를 매개변수로 받습니다. 이 구조체는 두 개의 스택(stack_a와 stack_b)과 관련 정보를 포함하고 있을 것으로 추정됩니다.

 

주요 변수
tmp: 현재 처리 중인 노드를 임시 저장
times: 반복 횟수를 추적
p1, p2: 두 개의 피벗 값
stacks->max_size: 전체 요소의 수

 

피벗 설정
p1 = stacks->max_size / 3;
p2 = (stacks->max_size / 3) * 2;

전체 요소 수를 3등분하여 두 개의 피벗을 설정합니다. p1은 하위 1/3 지점, p2는 상위 1/3 지점에 해당합니다.

 

메인 로직
함수는 stacks->max_size 만큼 반복하며 다음 작업을 수행합니다:
stack_a에서 상단 요소를 꺼냅니다 (pop_top 함수 사용).
꺼낸 요소의 값을 두 피벗과 비교합니다.

 

경우 1: 값이 p2보다 작은 경우
if (tmp->val < p2)
{
    push_top(stacks->stack_a, tmp);
    pb(stacks);
    if (tmp->val < p1)
        rb(stacks);
}
요소를 다시 stack_a에 넣습니다.
pb 함수를 호출하여 요소를 stack_b로 이동시킵니다.
만약 값이 p1보다 작다면, rb 함수를 호출하여 stack_b를 회전시킵니다.

 

경우 2: 값이 p2 이상인 경우
else
{
    push_top(stacks->stack_a, tmp);
    ra(stacks);
}

 

요소를 다시 stack_a에 넣습니다.
ra 함수를 호출하여 stack_a를 회전시킵니다.

 

결과
이 과정을 거치면 요소들이 다음과 같이 분류됩니다:
stack_b의 하단: val < p1인 요소들
stack_b의 상단: p1 <= val < p2인 요소들
stack_a: val >= p2인 요소들
이렇게 분류된 요소들은 이후의 정렬 과정에서 더 효율적으로 처리될 수 있습니다.

 

This function takes a pointer to a t_var structure named stacks as a parameter. This structure is presumed to contain two stacks (stack_a and stack_b) and related information.

Key Variables
tmp: Temporarily stores the node being processed
times: Tracks the number of iterations
p1, p2: Two pivot values
stacks->max_size: Total number of elements

 

Pivot Setting
p1 = stacks->max_size / 3;
p2 = (stacks->max_size / 3) * 2;
Two pivots are set by dividing the total number of elements into thirds. p1 corresponds to the lower 1/3 point, and p2 to the upper 1/3 point.

 

Main Logic
The function iterates stacks->max_size times, performing the following operations:
Removes the top element from stack_a (using the pop_top function).
Compares the value of the removed element with the two pivots.

 

Case 1: Value is less than p2
if (tmp->val < p2)
{
    push_top(stacks->stack_a, tmp);
    pb(stacks);
    if (tmp->val < p1)
        rb(stacks);
}

 

Puts the element back onto stack_a.
Calls the pb function to move the element to stack_b.
If the value is less than p1, calls the rb function to rotate stack_b.

 

Case 2: Value is greater than or equal to p2
else
{
    push_top(stacks->stack_a, tmp);
    ra(stacks);
}
Puts the element back onto stack_a.
Calls the ra function to rotate stack_a.

 

Result
After this process, the elements are classified as follows:
Bottom of stack_b: Elements with val < p1
Top of stack_b: Elements with p1 <= val < p2
stack_a: Elements with val >= p2
This classification of elements allows for more efficient processing in subsequent sorting steps.