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

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

이 함수 sort_args는 스택을 정렬하는 알고리즘을 구현한 것입니다.

함수 구조 분석
초기 설정
void sort_args(t_var *stacks)
{
    int a;
    int b;
함수는 t_var *stacks라는 구조체 포인터를 매개변수로 받습니다.
a와 b는 회전 연산에 사용될 정수형 변수입니다.

 

피벗 분할 및 초기 정렬
divide_pivot(stacks);
while (stacks->a_size > 3)
    pb(stacks);
divide_pivot 함수를 호출하여 스택을 피벗을 기준으로 분할합니다.
스택 A의 크기가 3보다 클 때까지 pb 함수를 반복 호출하여 요소를 스택 B로 이동시킵니다.

 

작은 크기 스택 처리
if (stacks->a_size == 2)
{
    if (stacks->stack_a->top->right->val > \
        stacks->stack_a->top->right->right->val)
        sa(stacks);
}
if (stacks->a_size == 3)
    sort_three_args(stacks);
스택 A의 크기가 2인 경우, 두 요소를 비교하여 필요시 sa 함수로 교환합니다.
스택 A의 크기가 3인 경우, sort_three_args 함수를 호출하여 정렬합니다.

 

메인 정렬 로직
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);
sort_big_last 함수를 호출하여 최종 정렬을 수행합니다.
주요 알고리즘 설명
피벗 분할: 초기에 스택을 피벗을 기준으로 분할하여 정렬의 효율성을 높입니다.
작은 크기 처리: 2개 또는 3개 요소에 대해 특별한 처리를 수행하여 간단히 정렬합니다.

 

반복적 정렬:
B 스택의 요소를 A 스택으로 최적의 위치에 삽입합니다.
각 삽입 시 최소 회전 횟수를 계산하고 실행합니다.
최종 정렬: 모든 요소가 A 스택으로 이동한 후, 최종적인 정렬을 수행합니다.
이 알고리즘은 효율적인 정렬을 위해 분할 정복 방식과 최적화된 회전 연산을 조합하여 사용하고 있습니다. 피벗을 이용한 초기 분할, 작은 크기의 특별 처리, 그리고 반복적인 최적 삽입을 통해 전체 정렬 과정을 최적화하고 있습니다.

 

This function sort_args is to implement an algorithm for sorting stacks.

Function Structure Analysis
Initial Setup
void sort_args(t_var *stacks)
{
    int a;
    int b;
The function takes a structure pointer t_var *stacks as a parameter.
a and b are integer variables used for rotation operations.

 

Pivot Division and Initial Sorting
divide_pivot(stacks);
while (stacks->a_size > 3)
    pb(stacks);
Calls the divide_pivot function to divide the stack based on a pivot.
Repeatedly calls the pb function to move elements to stack B until stack A's size is 3 or less.

 

Small Stack Handling
if (stacks->a_size == 2)
{
    if (stacks->stack_a->top->right->val > \
        stacks->stack_a->top->right->right->val)
        sa(stacks);
}
if (stacks->a_size == 3)
    sort_three_args(stacks);
If stack A's size is 2, compares the two elements and swaps them if necessary using the sa function.
If stack A's size is 3, calls the sort_three_args function to sort it.

 

Main Sorting Logic
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);
}

Loops while stack B is not empty.
Uses get_min_rotate to calculate the minimum number of rotations.
Rotates the stacks using rotate_same, rotate_a, and rotate_b functions.
Moves the top element from B to A using the pa function.

 

Final Sorting
sort_big_last(stacks);
Calls the sort_big_last function to perform the final sorting.
Key Algorithm Explanation
Pivot Division: Initially divides the stack based on a pivot to increase sorting efficiency.
Small Size Handling: Performs special processing for 2 or 3 elements to sort them simply.

 

Iterative Sorting:
Inserts elements from stack B into optimal positions in stack A.
Calculates and executes the minimum number of rotations for each insertion.
Final Sorting: Performs a final sort after all elements have been moved to stack A.
This algorithm combines a divide-and-conquer approach with optimized rotation operations for efficient sorting. It optimizes the overall sorting process through initial pivot-based division, special handling of small sizes, and iterative optimal insertions.