스택 정렬 알고리즘 | Stack sorting algorithm

스택 정렬 알고리즘 ❘ Stack sorting algorithm

sort_args는 스택 정렬 알고리즘입니다.

 

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

 

주요 단계
초기 분할
divide_pivot(stacks);
이 함수는 스택 A의 요소들을 피벗을 기준으로 분할합니다. 피벗보다 작은 요소들은 스택 B로 이동될 것으로 예상됩니다.

 

스택 A 크기 축소
while (stacks->a_size > 3)
    pb(stacks);
스택 A의 크기가 3 이하가 될 때까지 요소들을 스택 B로 옮깁니다. pb 함수는 "push to B"를 의미합니다.

 

소규모 정렬

 

스택 A의 크기가 2인 경우:
if (stacks->a_size == 2)
{
    if (stacks->stack_a->top->right->val > 
        stacks->stack_a->top->right->right->val)
        sa(stacks);
}

 

두 요소를 비교하여 필요한 경우 sa (swap A) 연산을 수행합니다.

 

스택 A의 크기가 3인 경우:
if (stacks->a_size == 3)
    sort_three_args(stacks);
3개 요소에 대한 특별한 정렬 함수를 호출합니다.

 

메인 정렬 루프
while (stacks->b_size)
{
    a = 0;
    b = 0;
    get_min_rotate(stacks, &a, &b);
    rotate_same(stacks, &a, &b);
    rotate_a(stacks, a);
    rotate_b(stacks, b);
    pa(stacks);
}

 

이 루프는 스택 B가 비어있을 때까지 반복됩니다:

 

get_min_rotate: 최소 회전 횟수를 계산합니다.
rotate_same: 두 스택을 동시에 회전시킵니다.
rotate_a와 rotate_b: 각 스택을 개별적으로 회전시킵니다.

pa: 스택 B의 top 요소를 스택 A로 이동시킵니다.

 

최종 정렬
sort_big_last(stacks);
마지막으로 대규모 정렬을 수행하는 함수를 호출합니다.

 

결론
이 알고리즘은 "분할 정복" 접근 방식을 사용합니다. 먼저 요소들을 두 스택으로 분할한 후, 작은 부분을 정렬하고, 그 다음 나머지 요소들을 효율적으로 병합하는 방식으로 동작합니다. 이는 퀵소트와 유사한 개념을 스택 기반 정렬에 적용한 것으로 볼 수도 있습니다.

 

This function sort_args is to implement a stack sorting algorithm. 

Function Overview
This function takes a structure pointer t_var *stacks as a parameter. This structure is presumed to contain two stacks (A and B) and related information.

 

Main Steps
Initial Partition
divide_pivot(stacks);
This function partitions the elements in stack A based on a pivot. Elements smaller than the pivot are expected to be moved to stack B.

 

Reduce Stack A Size
while (stacks->a_size > 3)
    pb(stacks);
Moves elements to stack B until the size of stack A is 3 or less. The pb function likely means "push to B".
Small-scale Sorting

 

When stack A has 2 elements:
if (stacks->a_size == 2)
{
    if (stacks->stack_a->top->right->val > 
        stacks->stack_a->top->right->right->val)
        sa(stacks);
}

 

Compares the two elements and performs an sa (swap A) operation if necessary.

 

When stack A has 3 elements:
if (stacks->a_size == 3)
    sort_three_args(stacks);
Calls a special sorting function for 3 elements.

 

Main Sorting Loop
while (stacks->b_size)
{
    a = 0;
    b = 0;
    get_min_rotate(stacks, &a, &b);
    rotate_same(stacks, &a, &b);
    rotate_a(stacks, a);
    rotate_b(stacks, b);
    pa(stacks);
}
This loop continues until stack B is empty:
get_min_rotate: Calculates the minimum number of rotations.
rotate_same: Rotates both stacks simultaneously.
rotate_a and rotate_b: Rotates each stack individually.
pa: Moves the top element from stack B to stack A.

 

Final Sorting
sort_big_last(stacks);

Finally, calls a function to perform large-scale sorting.

 

Conclusion
This algorithm uses a "divide and conquer" approach. It first partitions the elements into two stacks, then sorts the smaller portion, and efficiently merges the remaining elements. This is to apply a concept similar to quicksort to a stack-based sorting method.