push_swap 코드(퀵소트) a_to_b, b_to_a

퀵소트를 어떻게 할지 좀 더 자세하게 살펴보자

크게 2가지로 나뉜다.

1. a_to_b
2. b_to_a

이 함수 2개를 통해서 재귀를 엄청 돌린 뒤에 정렬을 마칠 것이다.

들어가전에 나의 헤더 파일

1. a스택과 b택을 따로 만들어줌

typedef struct s_node
{
	int				content;
	struct s_node	*prev;
	struct s_node	*next;
}	t_node;

typedef struct s_stack
{
	int					size;
	int					flag;
	struct s_node		*top;
	struct s_node		*bottom;
}	t_stack;

예제를 통해 살펴보자

1 3 2 8 7 4 5 9 10 6가 있는데 1 ~ 10으로 간단하게 말한다.

 

1. 그림 a_to_b

a_to_b 코드

이제 a_to_b를 세세하게 보자

 💡 매개변수 a스택, b스택, 스택 인자의 개수

void	a_to_b(t_stack **a, t_stack **b, int array_size)
{
	int	pivot1;
	int	pivot2;
	int	turn;
	int	ra_count;
	int	rb_count;
	int	pb_count;
	int stack_a_count;

//a 스택이 만약 정렬되어 있으면 함수 끝
	if (check_sorted((*a)->top, array_size, A))
		return ;
//변수 초기화
	ra_rb_pb_reset(&ra_count, &rb_count, &pb_count);
//a 스택 인자 개수
	stack_a_count = stack_top_count(a);
//매개변수로 들어온 인자가 3이하면 정렬
	if (array_size <= 3)
		return (three_underonly_fuc_a(a, array_size));
//피봇 구하기
	pivot1 = pivot_answer(a, array_size);
	pivot2 = pivot_answer2(a, array_size);

//매개변수로 받은 만큼 while문을 돌려서 b스택으로 보내주기
	turn = 0;
	while (turn < array_size)
	{
		if ((*a)->top->content >= pivot1)
			sort_alogorithm_ra(a, &ra_count);
		else
		{
			sort_alogorithm_pb(a, b, &pb_count);
			if ((*b)->top->content > pivot2)
			{
				rb(b);
				rb_count++;
			}
		}
		turn++;
	}
//b스택에 보낸 친구들 중에 중간 친구들 위로 올리기
	rrb_a_to_b(rb_count, b, turn);
//b_to_a에서 보낸 것들 중 ra 시킨 친구들 위로 올리기
	while (turn < ra_count)
	{
		if (stack_a_count != array_size)
		{
			if (turn < ra_count)
				rra(a);
		}
		turn++;
	}

//인자가 3개 이하 남을 때 까지 돌려야하는데 그 개수를 아는 거는 ra_count
	a_to_b(a, b, ra_count);	
}

• check_sorted는 인자가 스택이 정렬되어 있는지 보는 함수
• three_underonly_fuc_a는 인자가 3개 이하면 정렬을 하는데 하드코딩을 하면 된다 3개일 때, 2개 일 때 각각해주면 된다.
• sort_alogorithm_ra, sort_alogorithm_pb은 각각 ra를 하거나 pb를 하고 ra_count, pb_count를 올려준다.
• rrb_a_to_b는 지금 while문을 보면 중간 친구들을 rb를 해서 내려주는데 내려준 만큼 rrb를 시키는 함수이다
• while (turn < ra_count) 이 부분은 b_to_a 때문에 필요하다

그러면 이제 a_to_b 재귀는 끝났고 b_to_a 재귀를 돌려야한다.

• 생각을 해보자

우리가 ra_count로 큰 친구들은 끝이 났다 그러면 이제 남은 건?

→ 중간 친구들과 작은 놈들이다.

이렇게 재귀를 넣어주면 된다

	b_to_a(a, b, rb_count);
	b_to_a(a, b, pb_count - rb_count);

a_to_b 최종 코드

→ 이 최종 코드는 최적화를 한 것이 아니기 때문에 완벽한 것은 아니다.

void	a_to_b(t_stack **a, t_stack **b, int array_size)
{
	
int	pivot1;
	int	pivot2;
	int	turn;
	int	ra_count;
	int	rb_count;
	int	pb_count;
	int stack_a_count;

//a 스택이 만약 정렬되어 있으면 함수 끝
	if (check_sorted((*a)->top, array_size, A))
		return ;
//변수 초기화
	ra_rb_pb_reset(&ra_count, &rb_count, &pb_count);
//a 스택 인자 개수
	stack_a_count = stack_top_count(a);
//매개변수로 들어온 인자가 3이하면 정렬
	if (array_size <= 3)
		return (three_underonly_fuc_a(a, array_size));
//피봇 구하기
	pivot1 = pivot_answer(a, array_size);
	pivot2 = pivot_answer2(a, array_size);

//매개변수로 받은 만큼 while문을 돌려서 b스택으로 보내주기
	turn = 0;
	while (turn < array_size)
	{
		if ((*a)->top->content >= pivot1)
			sort_alogorithm_ra(a, &ra_count);
		else
		{
			sort_alogorithm_pb(a, b, &pb_count);
			if ((*b)->top->content > pivot2)
			{
				rb(b);
				rb_count++;
			}
		}
		turn++;
	}
//b스택에 보낸 친구들 중에 중간 친구들 위로 올리기
	rrb_a_to_b(rb_count, b, turn);

//인자가 3개 이하 남을 때 까지 돌려야하는데 그 개수를 아는 거는 ra_count
	a_to_b(a, b, ra_count);	
	b_to_a(a, b, rb_count);
	b_to_a(a, b, pb_count - rb_count);
}

 

b_to_a

 

b_to_a도 똑같다.

1. 인자가 3개 이하면 정렬하고 pa를 해줌.
2. 4개 이상이라면 피봇 구하고 다시 while문으로 나눈다.

b_to_a는 보가 쉽게 바꿨다.

void	b_to_a(t_stack **a, t_stack **b, int array_size)
{
	(*a)->flag = 0;
	int	pivot1;
	int	pivot2;
	int	turn;
	int	rb_count = 0;
	int	ra_count = 0;
	int	pa_count = 0;
	int stack_b_count;

//정렬되어 있으면 인자 만큼 pa
	if (check_sorted((*b)->top, array_size, B))
	{
		while (array_size-- > 0)
			pa(a, b);
		return ;
	}
	stack_b_count = stack_top_count(b);

//3개 이하면 정렬한 후에 pa하기
	if (array_size <= 3)
	{
			three_underonly_fuc_b(b, array_size);
			while (array_size-- > 0)
				pa(a, b);
		return ;
	}

//피봇 구하기
	pivot1 = pivot_answer(b, array_size);
	pivot2 = pivot_answer2(b, array_size);
	turn = 0;
	while (turn < array_size)
	{
		if ((*b)->top->content < pivot2)
		{
			rb(b);
			rb_count++;
		}
		else
		{
			pa(a, b);
			pa_count++;
			if ((*a)->top->content < pivot1)
			{
					ra(a);
				ra_count++;
			}
		}
		turn++;
	}
	a_to_b(a, b, pa_count - ra_count);
	turn = -1;
	while (++turn < ra_count)
		rra(a);
	a_to_b(a, b, ra_count);
	turn = -1;
	while (++turn < rb_count)
		rrb(b);
	b_to_a(a, b, rb_count);
}

이제 재귀 부분이 문제인데

• a_to_b(a, b, pa_count - ra_count);
  • 이 부분은 b_to_a에서 while문을 돌렸을 때 가장 큰 친구들이다
• a_to_b(a, b, ra_count);
  • 이 부분은 b_to_a에서 while문 돌렸을 중간 친구들이다
• b_to_a(a, b, rb_count);
  • 이 부분은 b_to_a에서 while문 돌렸을 작은 친구들이다

a_to_b 흐름과 b_to_a 흐름을 보여주었다 여기까지만 와도 80프로 한 거!

다시 간략하게 설명해보자

• a_to_b 함수 → a에 큰 거, b 위에는 작은 거, 밑에는 중간
  • b_to_a로 들어가기 전 rrb == 중간 친구들을 top으로 올리기 위해
• b_to_a → a에서 받은 중간 친구들을 while문으로 나눈다
  • a_to_b(a, b, pa_count - ra_count); == a 스택 위에 큰 거 정렬
  • a_to_b(a, b, ra_count); == a 스택 있는 중간 친구들을 정렬
  • b_to_a(a, b, rb_count); == b 스택 있는 작은 친구들을 정렬
• b_to_a(a, b, pb_count - rb_count); == a에서의 작은 친구들 정렬
  • b_to_a 반복