[push_swap] 정렬하기

구현 알고리즘

• 배열에있는 값중 중간값을 찾아 피봇으로 사용하는 퀵소트를 구현
• 값들의 이동을 위한 명령어는 바로 출력되지않고 최적화를 위해 별도 저장공간에 저장됨

순서

1. 중간값을 찾기위해 임의의 리스트에 정렬할 숫자들을 복사하고 임의로 정렬하여 중간값을 추출
2. a스택에서 중간값을 기준으로 작은값은 a스택, 크거나 같은 값들은 b스택으로 보내주는 atob() 호출
3. 정렬해야할 값이 2개 이하가 될 때 까지 atob를 재귀로 호출
4. 정렬해야할 값이 2개 이하라면 atob재귀를 멈추고 해당 값을 정렬하고 함수를 나오며 btoa() 호출
5. b스택에서 중간값을 기준으로 작은값은 a스택, 크거나 같은 값들은 b스택으로 보내줌 (btoa())
6. 더이상 정렬할 값이 없을때까지 다시 2부터 반복

구현

int	start_sort(t_deque *deq_a, t_deque *deq_b, t_deque *deq_str)
{
	if (deq_a->first == deq_a->last) // 값이 없거나 1개뿐일때 종료
		return (0);
	if (is_sorted(deq_a)) // 이미 정렬되어있다면 종료
		return (0);
	else if (deq_a->size == 2) // 2개뿐일 때
		do_sa(deq_a, deq_str);
	else if (deq_a->size == 3) // 3개뿐일 때
		sort_3(deq_a, deq_str);
	else if (deq_a->size == 4) // 4개 뿐일 때
		sort_4(deq_a, deq_b, deq_str);
	else if (deq_a->size == 5) // 5개 뿐일 때
		sort_5(deq_a, deq_b, deq_str);
	else // 6개 이상일 때
		atob(deq_a, deq_b, deq_str, deq_a->size);
	return (0);
}

atob(a스택, b스택, 명령어를 저장할 스택, 정렬할 값의 갯수)

void	atob(t_deque *deq_a , t_deque *deq_b, t_deque *deq_str, int r)
{
	t_param	param; // ra,rb,pa,pb 호출 횟수와 반복횟수를 저장하는 값들의 구조체

	set_param(&param); // 구조체 값들을 초기화
	if (r == 1) // 확인할 값이 1개라면 (재귀 x)
		do_ra(deq_a, deq_str);
        //지금까지 정렬된 값 앞쪽에 pa명령을 통해 넘어온 값이므로 ra하여 뒤로 밀어줌
        //ex) [2, 3, 4] [6, 8, 7] -> [6, 2, 3, 4] [8, 7] -> [2, 3, 4, 6] [8, 7]
	else if (r == 2) // 확인할 값이 2개라면 (재귀 x)
		atob_2(deq_a, deq_str); //2개일때 값을 정렬하는 함수 호출
	else // 확인할 값이 3개 이상이라면 (재귀 o)
	{
		param.pivot = get_pivot(deq_a, r);
        // 정렬해야할 값들의 중간값을 반환받아 피봇으로 활용함
		while (++param.i < r) // r만큼 반복
		{
			param.curr = deq_a->first;
			if (param.curr->num < param.pivot) // 피봇보다 현재값이 작다면
				param.ra += do_ra(deq_a, deq_str);
                // ra명령어로 a스택의 뒤로 넘겨주고 ra호출횟수를 늘림(a스택에 남겨둔 값의 갯수)
			else // 피봇보다 크거나 같다면
				param.pb += do_pb(deq_a, deq_b, deq_str);
                // pb명령어로 b스택에 넘겨주고 pb카운트를 늘림 (b스택에 넘겨줌 값의 갯수)
		}
		param.i = -1;
		while (++param.i != param.ra && deq_a->do_first != 1)
        // 첫 호출이 아닐때, 또한 ra로 넘겨준 갯수만큼 반복
			do_rra(deq_a, deq_str);
            // ra로 뒤로넘긴 값들을 rra로 다시 앞으로 넘겨줌
		deq_a->do_first = 0;
        // 첫 호출인지 아닌지 확인하는 값을 0으로 바꿔 첫 호출이 아닌것으로 설정
		atob(deq_a, deq_b, deq_str, param.ra);
        //atob를 재귀로 호출하고 ra는 이번에 a에 남겨뒀던 값들의 수
		btoa(deq_a, deq_b, deq_str, param.pb);
        //atob가 더이상 나오지 않으면 btoa를 호출하고 pb는 이번 atob호출때 b로 넘겨줬던 값들의 수
	}
}

void	atob_2(t_deque *deq_a, t_deque *deq_str) // atob에서 정렬할 값이 2개일 때 호출
{
	if (deq_a->first->num > deq_a->first->next->num)
    // 첫 값이 두번째 값보다 클 때 [8, 7, 1, 2, 3]
		do_sa(deq_a, deq_str); // sa호출 [7, 8, 1, 2, 3]
	do_ra(deq_a, deq_str); // 앞의 값을 뒤로 돌리기위해 ra 호출 [8, 1, 2, 3, 7]
	do_ra(deq_a, deq_str); // [1, 2, 3, 7, 8]
}

btoa(a스택, b스택, 명령어를 저장할 스택, 정렬할 값의 수)

void	btoa(t_deque *deq_a, t_deque *deq_b, t_deque *deq_str, int r)
{
	t_param	param; // ra,rb,pa,pb 호출 횟수와 반복횟수를 저장하는 값들의 구조체

	set_param(&param); // 구조체 값들을 초기화
	if (r == 1) // 확인할 값이 1개라면 (재귀 x)
		do_pa(deq_a, deq_b, deq_str);
        // 해당 값은 현재 b스택내의 최소값이므로 pa명령어로 a스택에 보내줌
	else if (r == 2) // 확인할 값이 2개라면 (재귀 x)
		btoa_2(deq_a, deq_b, deq_str);
        // 2개일때의 필요명령어를 호출하는 함수 호출
	else // 확인할 값이 3개 이상이라면 (재귀 o)
	{
		param.pivot = get_pivot(deq_b, r);
		while (++param.i < r) // r만큼 반복
		{
			param.curr = deq_b->first;
			if (param.curr->num >= param.pivot)
            // 현재의 값이 피봇보다 크거나 같다면
				param.rb += do_rb(deq_b, deq_str);
                // rb명령어로 b스택의 뒤로 보내고 rb카운트 추가
			else // 현재 값이 피봇보다 작다면
				param.pa += do_pa(deq_a, deq_b, deq_str);
                // pa명령어로 a스택에 보내고 pa카운트 추가
		}
		param.i = -1;
		while (++param.i != param.rb)
        // rb로 뒤로 보낸만큼 다시 rrb로 앞에 보내줌
			do_rrb(deq_b, deq_str);
		atob(deq_a, deq_b, deq_str, param.pa); // a로 보낸 갯수만큼 다시 atob 호출
		btoa(deq_a, deq_b, deq_str, param.rb);
        // a에 정렬이 완료되어 b에 남긴 갯수만큼  btoa 호출
	}
}

void	btoa_2(t_deque *deq_a, t_deque *deq_b, t_deque *deq_str)
{
	if (deq_b->first->num > deq_b->first->next->num)
    // b스택 첫값이 두번째값보다 크다면 [1, 2, 3, 4] [7, 6]
		do_sb(deq_b, deq_str);
        //sb를 호출하여 순서를 바꿔줌 [1, 2, 3, 4] [6, 7]
	do_pa(deq_a, deq_b, deq_str); // pa로 첫 값을 a에 보내줌 [6, 1, 2, 3, 4] [7]
	do_ra(deq_a, deq_str); // ra로 a스택 첫 값을 마지막으로 보내줌[1, 2, 3, 4, 6] [7]
	do_pa(deq_a, deq_b, deq_str); // pa로 첫 값을 a에 보내줌 [7, 1, 2, 3, 4, 6]
	do_ra(deq_a, deq_str); // ra로 a스택 첫 값을 마지막으로 보내줌[1, 2, 3, 4, 6, 7]
}