[pushswap]정렬 알고리즘

JH Bang·2022년 6월 20일

push_swap

42 Seoul

목록 보기

3/9

푸시스왑은 정렬 알고리즘과 복잡도 개념에 대해 공부할 수 있는 과제이다.

1피봇으로 개념잡기

퀵소트를 2피봇을 잡아서 구현해보던 중 문제점 발견함. rra, rrb 하기 전에 재귀로 들어가서 정렬 된 다음에 rra, rrb 과정이 나와야한다는 점을 깨달음.
무작위 int 값을 프로그램에 넣으면, 파싱한다음 배열에 저장해서 indexing하는 것과, 숫자를 정렬해서 인덱싱한 것 까지 완료. 이제 리스트를 이용해 디큐랑 스택이랑 혼합된 형태의 자료구조를 만들어야 함.

감이 전혀 안 오는 사람은 다음 1피봇짜리를 손으로 그려보면 도움이 됨. 시간이 되면 2피봇 짜리도 직접 그려보는 것을 추천.

스택 저장

다음과 같이 스택을 담을 수 있는 ft_stack_push 함수를 만들었다.

#include "push_swap.h"

void	ft_stack_push(int *index, t_list **p_stack)
{
	t_list	*tmp;
	//t_list	*print_lst;

	//ft_printf("index address: %p\n", index);
	tmp = ft_lstnew(index);
	if (!tmp)
	{
		ft_printf("Error\n");
		exit(0);
	}
	//ft_printf("%d\n", *((int *)tmp->content));
	ft_lstadd_front(p_stack, tmp);
    //들어간 자료 확인
	// print_lst = *p_stack;
	// while (print_lst)
	// {
	// 	ft_printf("stack: %d\n", *((int *) print_lst->content));
	// 	print_lst = print_lst->next;
	// }
}

여기서 중요한 건, 함수의 인자를 주소값이 다르게 하도록 넘겨줘야 하는 점이다.
즉, 아래와 같이

	while (i < k)
	{
		stacked[i] = ft_find_index(parsed[i], indexed, k);
		ft_stack_push(&stacked[i], &stack);
		ft_printf("index : %d\n", stacked[i]);
		i++;
	}

stacked[] 배열을 이용해 들어가는 자료(여기서는 인덱스)의 주소값을 다르게 만들었다.
만약 stacked[i] 대신에 int idx 를 선언하고 idx를 넘겨주게 되면 주소값이 바뀌지 않게 된다. 노드 수만 늘어나고 각 노드 안의 content포인터는 같은 자료를 가리키게 되는 대참사가 일어난다.

이는 함수가 스택 메모리를 사용하는 특성 때문으로, 함수 호출이 종료되고 메모리를 반환하고, 다시 호출하면 같은 메모리 공간을 사용하게 되면서 발생하는 문제이다.

연결리스트 Logic

이번에는 과제에서 요구하는 명령어들을 함수로 구현해 줄 차례이다.

pa : b의 top노드를 a top쪽으로 push
pb : a의 top노드를 b top쪽으로 push
ra : a의 top노드를 bottom으로 rotate
rb : b의 top노드를 bottom으로 rotate
rr = ra + rb
rra : a의 bottom노드를 top으로 reverse rotate
rrb : b의 bottom노드를 top으로 reverse rotate
rrr = rra + rrb
sa : a의 top 부분 두 노드의 위치를 swap
sb : b의 top 부분 두 노드의 위치를 swap
ss = sa + sb

stack(deque구조지만 편의상)을 a를 기준으로 하고 대충 수도 코드를 짜보면,

sa

tmp = stack->next;
stack->next = stack->next->next;
tmp->next = stack;
stack = tmp;

ra

tmp = stack->next;
last = ft_lstlast(stack_a);
stack_a->next = NULL;
last->next = stack_a;
stack_a = tmp;

rra

last = ft_lstlast(stack_a);
new_last = ft_get_newlast(stack_a);
last->next = stack_a;
stack_a = last;
new_last->next = NULL;

pb

tmp = stack_a->next;
if (stack_b == NULL)
	tmp2 = NULL;
else
	tmp2 = (stack_b)->next;
tmp2 = stack_b->next;
stack_b = stack_a;
stack_b->next = tmp2;
stack_a = tmp;

대충 쓴거라 세부적인 구현 과정에서 수정해야할 부분이 있을 수도 있는데 대충 이런 느낌이다 정도만 알고 구현 들어가면 된다.
나머지 명령어나 이런거는 조합해서 만들면 된다.

Final logic

t_stack구조체에 명령어 스택 및 A,B 스택을 구현해주고 2피봇을 설정, 피봇을 기준으로 세 덩어리로 나누고 재귀로 들어가는 퀵소트 로직을 적용하였다.
최적화를 위해 2개 및 3개일 때 정렬을 하드코딩 해주면 된다.

void	logic_on_a(t_stack *stk, int k, int min)
{
	t_pos	pos;
	t_cnt	cnt;

	if ((stk)->a == NULL || k == 0)
		return ;
	if (ft_is_sorted_chunk((stk)->a, k))
		return ;
	if (k == 1 || k == 2 || k == 3)
	{
		case_by_case_a(stk, k);
		return ;
	}
	else
	{
		ft_set_cnt_zero(&cnt);
		pos.pv1 = (k / 3) + min + 1;
		pos.pv2 = 2 * (k / 3) + min + 1;
		chunk_div_a(stk, pos, &cnt, k);
	}
	chunk_rrr_a(stk, &cnt);
	logic_on_a(stk, cnt.ra, pos.pv2);
	logic_on_b(stk, cnt.rb, pos.pv1);
	logic_on_b(stk, cnt.pb - cnt.rb, pos.pv1 - (k / 3));
}

void	logic_on_b(t_stack *stk, int k, int min)
{
	int		i;
	t_pos	pos;
	t_cnt	cnt;

	if ((stk)->b == NULL || k == 0)
		return ;
	else if (ft_is_rev_sorted_chunk((stk)->b, k))
	{
		i = -1;
		while (++i < k)
			do_push(&(stk)->op, &(stk)->b, &(stk)->a, "a");
	}
	else if (k == 1 || k == 2 || k == 3)
		case_by_case_b(stk, k);
	else
	{
		ft_set_cnt_zero(&cnt);
		pos.pv1 = k / 3 + min - 1;
		pos.pv2 = 2 * (k / 3) + min - 1;
		chunk_div_b(stk, pos, &cnt, k);
		logic_on_a(stk, cnt.pa - cnt.ra, pos.pv2);
		chunk_rrr_b(stk, &cnt);
		logic_on_a(stk, cnt.ra, pos.pv1);
		logic_on_b(stk, cnt.rb, pos.pv1 - (k / 3));
	}
}

1~5개일 때 하드코딩

이 외에도 1~5개 케이스일 때 2피봇을 적용하면 명령어 수가 되레 많아지므로 하드코딩을 해줘야 한다. 1개~4개는 케이스별로 잘 코딩 해주면 되고, 5개일 때가 좀 까다로울 수 있다.
내 경우는 가장 작은 수와 큰 수만 pb해주고, 3개 짜리 정렬 로직을 적용한 뒤 다시 하나씩 정렬해주는 방식을 사용했다.