push_swap에서의 quick_sort

push_swap 과제에서 quick sort의 차이점

퀵 정렬은 기본적으로 배열에서 정렬하는것을 가정하고 정렬한다 그러나 push_swap과제에서는 stack을 이용해서 정렬을 진행해야 하는데 고려해야할 점들이 있다

• 정렬을 하며 이용할 수 있는공간이 Stack A, Stack B 두개만 존재한다
• 각 Stack의 Top, Bottom에서만 원소에 접근이 가능하다
• 과제에서 주어진 명령어로만 동작해야 한다

이에따라 과제에서 이루어지는 퀵 정렬은 pivot을 기준으로 나누는 작업을 반복하여 정렬을 시킨다 이 때 기존 퀵정렬은 재귀를 한번 반복할 때 마다 pivot을 위치가 고정이 되었지만 push_swap과제에서는 값을 저장해 놓을 공간이 애매하여 pivot또한 위치가 고정이 아닌 재귀범위에 포함되어져서 동작되게된다

과제 Quick_sort flow

flow chart를 바탕으로 작성된 코드

quick_sort_a

void	quick_sort_a(t_dlist *stack_a, t_dlist *stack_b, t_command_dlist \
*stack_command, t_sort_var sort_var)
{
	t_sort_var	next_sort_var;

	sort_var_init(&sort_var, 1);
	if (quick_sort_size_check(stack_a, stack_b, stack_command, sort_var))
    // size가 3이하이면 정렬(하드코딩)후 재귀를 종료한다
		return ;
	stack_div_a(stack_a, stack_b, stack_command, &sort_var);
    // pivot을 기준으로 데이터들을 나눠준다
	stack_rrr(stack_a, stack_b, stack_command, &sort_var);
    // stack bottom에 임시로 보관했던 값들을 top으로 올려준다
	next_sort_var.size = sort_var.current_up_cnt;
	next_sort_var.upper = sort_var.upper;
	quick_sort_a(stack_a, stack_b, stack_command, next_sort_var);
    // size를 기존 size의 1/3만큼 설정해서 재귀함수를 호출한다
	next_sort_var.size = sort_var.next_up_cnt;
	next_sort_var.upper = sort_var.upper + 1;
	quick_sort_b_push_a(stack_a, stack_b, stack_command, next_sort_var);
    k_command, next_sort_var);
    // size를 기존 size의 1/3만큼 설정해서 재귀함수를 호출한다
	next_sort_var.size = sort_var.next_down_cnt;
	quick_sort_b_push_a(stack_a, stack_b, stack_command, next_sort_var);
    k_command, next_sort_var);
    // size를 기존 size의 1/3만큼 설정해서 재귀함수를 호출한다
}

quick_sort_b

void	quick_sort_b_push_a(t_dlist *stack_a, t_dlist *stack_b, \
t_command_dlist *stack_command, t_sort_var sort_var)
{
	t_sort_var	next_sort_var;

	sort_var_init(&sort_var, 2);
	if (quick_sort_size_check(stack_b, stack_a, stack_command, sort_var))
    // size가 3이하이면 정렬(하드코딩)후 a로 push해준다
		return ;
	stack_div_b(stack_b, stack_a, stack_command, &sort_var);
    // pivot을 기준으로 데이터들을 나눠준다
	next_sort_var.size = sort_var.next_up_cnt;
	next_sort_var.upper = sort_var.upper + 1;
	quick_sort_a(stack_a, stack_b, stack_command, next_sort_var);
    // size를 기존 size의 1/3만큼 설정해서 재귀함수를 호출한다
	stack_rrr(stack_b, stack_a, stack_command, &sort_var);
    // stack_bottom에 임시로 보관했던 값들을 top으로 올려준다
	next_sort_var.size = sort_var.next_down_cnt;
	quick_sort_a(stack_a, stack_b, stack_command, next_sort_var);
    // size를 기존 size의 1/3만큼 설정해서 재귀함수를 호출한다
	next_sort_var.size = sort_var.current_up_cnt;
	next_sort_var.upper = sort_var.upper;
	quick_sort_b_push_a(stack_a, stack_b, stack_command, next_sort_var);
    // size를 기존 size의 1/3만큼 설정해서 재귀함수를 호출한다
}