42 push_swap (5)

push_swap에서 merge sort를 구현한 과정입니다.
merge sort알고리즘은 아래의 노션을 참고했습니다.

Push Swap 병합정렬로 해결하기

위의 노션을 읽고 나서 코드를 작성하려고 하면 몇 가지 의문이 생깁니다.

• 그래서 지금 만들어야 하는 삼각형의 크기는?
• 그 삼각형의 방향은 어떻게 되는가?
• a에 만들어야 하는가 b에 만들어야 하는가?

이 의문을 해결하기 위해 삼각형을 다시 살펴보겠습니다.
하나의 커다란 삼각형을 depth0으로 하고 쪼개질 수록 depth가 증가한다고 하겠습니다.

depth=n이라고 한다면
총 $3^n$개의 삼각형이 있을것입니다. 여기서 i번째 삼각형의 방향을 dir[n, i], 크기를 amt[n, i] 라고 한다면 다음과 같은 관계식을 얻을 수 있습니다.
i ) $0\leq i\lt3^{n-1}$

• $dir[n, i] = dir[n-1, i]$
• $amt[n, i] = amt[n-1, i]\div3$

ii ) $3^{n-1}\leq i\lt2\cdot3^{n-1}$

• $dir[n, i] = dir[n-1, 2\cdot3^{n-1}-1-i]$
• $amt[n, i] = amt[n-1, 2\cdot3^{n-1}-1-i]\div3$

iii ) $2\cdot3^{n-1}\leq i\lt3^n$

• $dir[n, i] = ~dir[n-1, 3^{n-1}-1-i]$
• $amt[n, i] = amt[n-1, 3^{n-1}-1-i]\div3$

그리고 dir[0,0]=1, amt[0,0]=n임을 알고있습니다. 따라서 현재 만드는 모양의 depth, i, 전체개수 n이 주어진다면 크기와 방향을 알려주는 다음과 같은 함수를 만들 수 있습니다.

int	calc_direction(int depth ,size_t i, size_t n)
{
	if (depth == 0)
    	return (1);
    else if (i < pow(3, depth - 1))
    	return (calc_direction(depth - 1, i, n);
    else if (i < 2 * pow(3, depth - 1))
    	return (!calc_direction(depth - 1, (2 * pow(3, depth - 1)) - 1 - i, n);
    else
    	return (!calc_direction(depth - 1, (3 * pow(3, depth - 1)) - 1 - i, n);
}

size_t	calc_amount(int depth, size_t i, size_t n)
{
	if (depth == 0)
    	return (n);
    else if (i < pow(3, depth - 1))
    	return (calc_amount(depth - 1, i, n) / 3);
    else if (i < 2 * pow(3, depth - 1))
    	return (calc_amount(depth - 1, (2 * pow(3, depth - 1)) - 1 - i, n);
    else
    	return (calc_amount(depth - 1, (3 * pow(3, depth - 1)) - 1 - i, n);     
}

calc_dieection 에서 n은 전혀 사용되지 않고, 두 함수 모두에서 depth는 pow의 인자로만 계산됩니다. 또한 calc_amount같은 경우는 저대로 계산할 경우 n이 3의 거듭제곱이 아닌 이상 원래보다 같거나 적은 값을 내보낼 것입니다. 따라서 다음과 같이 수정할 수 있습니다.

int	calc_direction(size_t pow, size_t i)
{
	if (pow == 1)
    	return (1);
    else if (i < pow / 3)
    	return (calc_direction(pow / 3, i);
    else if (i < 2 * pow / 3)
    	return (!calc_direction(pow / 3, 2 * pow / 3 - 1 - i);
    else
    	return (!calc_direction(pow / 3, pow - 1 - i);
}

size_t	calc_amount(size_t pow, size_t i, size_t n)
{
	size_t	tmp;

	if (pow == 1)
    	return (n);
    else if (i < pow / 3)
    	return (calc_amount(pow / 3, i, n) / 3);
    else if (i < 2 * pow / 3)
    {
    	tmp = calc_amount(pow / 3, 2 * pow / 3 - 1 - i, n);
    	return (tmp / 3 + (tmp % 3 > 1));
    }
    else
    {
    	tmp = calc_amount(pow / 3, pow - 1 - i, n);
    	return (tmp / 3 + (tmp % 3 > 0));
    }

또한 이렇게 depth에 대한 약속을 하고 나면 depth가 홀수일 때 A,짝수일 때 B에 모양을 만들어야 한다는 것 도 알 수 있습니다.

다만 지금 모습은 $\frac53nlog_3n$의 복잡도를 위해서 처음 모양을 만들 때 들어가는 횟수를 무시하고있습니다. 따라서 n이 작아질 수록 비효율적이 되므로 작은 수는 다른 방식을 사용하여야 합니다.
저는 n이 6이하일 때를 기준으로 잡았습니다.

• n=1
  정렬이 필요하지 않습니다.
• n=2
  top > next 리면 sa를 수행합니다.
• $n=3$
  top이 가장 크다면 ra, next가 가장 크다면 rra를 하여 가장 큰 값이 bottom에 오도록 합니다.
  top이 next보다 작다면 sa를 수행합니다.
• n=4 ~ 6
  A에 3개의 수만 남기고 B로 이동합니다.
  A는 정방향 정렬, B는 역방향 정렬합니다. n=1~3을 참고합니다.
  A와 B를 merge sort합니다.

위의 과정을 수행하면 6이하의 n에 대해서 다음과 같은 횟수가 보장됩니다.

n	횟수
2	0~1
3	0~2
4	5~7
5	7~10
6	9~13