42seoul:: Push Swap - 퀵소트 알고리즘을 통한 정렬

jahlee·2023년 2월 24일
0

개인 공부

목록 보기
8/23
post-thumbnail

퀵 소트 (quick sort) 알고리즘

퀵 소트 알고리즘을 간단하게 설명 하자면, 수열에서 피봇을 하나 골라준다음 다른 수들과 비교하여 해당 피봇 보다 작으면 왼쪽, 크면 오른쪽으로 보낸다. 이때 보장할 수 있는 사실은 피봇을 기준으로 왼쪽은 무조건 피봇보다 작다는 점과 오른쪽은 무조건 크다는 점이다. 이렇게 나누어진 두 영역에 대해 각각 새로운 피봇을 정해주고 이전 과정을 계속 반복해 주면 된다. 이를 분할 정복 방식이라고도 한다.
퀵 소트 정렬에서 피봇을 어떻게 설정하느냐에 따라 성능차이가 날 수 있다.

정렬 과정 예시

depth614325
pivot
1614325
pivot(1)pivot(2)
2132465
======영역1======<분할정복>====영역2=====
3123456

Push Swap 에 퀵 소트 알고리즘 적용

퀵 소트 알고리즘의 경우 분할정복으로 정렬을 하는 방식이기 때문에 재귀적인 방식으로 코드를 작성하면 된다. 피봇의 경우 하나만 잡아도 되긴하지만 더빠른 정렬을 위해 2개의 피봇을 잡는 방식으로 코드를 구현했다. 위에서 말했듯이 피봇을 어떻게 설정하느냐가 동작횟수의 효율을 정하기 때문에 잘 골라 주어야한다.
구현한 코드에서는 범위 size내에서 size/3번째로 큰값을 작은 피봇(sp), (size*2)/3번째로 큰값을 큰 피봇(bp)로 정해주었다.

함수에 따른 이동 구조

- a_to_b

pb <= sp < pb && rb < bp <= ra
3분할 했을때 크거나 같으면 ra
중간값이면 pb && rb
작거나 같으면 pb

- b_to_a

rb <= sp < pa && ra < bp <= pa
3분할 했을때 크거나 같으면 pa
중간값이면 pa && ra
작거나 같으면 rb

중간값을 범위가 가장 작은 이유는 나중에 다시감아 올릴때의 명령어를 최소화 하기 위해서 이다.

핵심 코드 구조

void	a_to_b(t_stack *st_a, t_stack *st_b, int size)
{
	int	arr[3];

	arr[0] = 0;//큰값
	arr[1] = 0;//중간값
	arr[2] = 0;//작은값
	if (size <= 3)//3개 이하일때 하드코딩
	{
		st_under_three(st_a, st_b, st_a, size);
		return ;
	}
	if (is_sorted(st_a, size, 1))
		return ;
	a_to_b_func(st_a, st_b, size, arr);//3분할해준다.
	a_to_b(st_a, st_b, arr[0]);
	b_to_a(st_a, st_b, arr[1]);
	b_to_a(st_a, st_b, arr[2]);
}
void	b_to_a(t_stack *st_a, t_stack *st_b, int size)
{
	int	arr[3];

	arr[0] = 0;//큰값
	arr[1] = 0;//중간값
	arr[2] = 0;//작은값
	if (size <= 3)//3개이하일떄 하드코딩
	{
		st_under_three(st_a, st_b, st_b, size);
		return ;
	}
	b_to_a_func(st_a, st_b, size, arr);//3분할
	a_to_b(st_a, st_b, arr[0]);
	b_to_a_reverse(st_a, st_b, arr[1], arr[2]);//중간값 되감아서 올려주기
	a_to_b(st_a, st_b, arr[1]);
	b_to_a(st_a, st_b, arr[2]);
}

정렬 과정 예시

노란색으로 하이라이트 된값이 피봇이다.

구현할때 주의할 점들

  1. 인자를 받아줄때 문자열로 받는 부분에 대한 처리도 해주자.
    ex) ./push_swap "3 2" 1
  2. 인자의 범위(정수범위)에 대한 판별을 해줄때 atoi를 해주는 문자열의 길이와 정수길이에 대한 체크를 하자.
  3. 빈문자열 이나 유효한 숫자가 아닐때도 조심하자
    ex) ./push_swap "3 2-" ""
  4. 유효한 동작 명령인지도 체크를 해주자. ft_strncmp사용하는걸 추천
  5. 만점 기준
    3개 -> 2개이하
    5개 -> 12이하
    100개 -> 700이하
    500개 -> 5500이하
  6. 퀵소트의 경우 피봇을 잘정해주어야 100개 만점을 받을 수 있다.
  7. 보너스부분에서 이미 정렬된 값이 들어온 경우에는 명령을 받아주어야 한다. mandatory부분 처럼 아무것도 동작하지않고 종료되면 안된다.
  8. !!!메모리 누수 조심!!!
  9. norminette 체크

0개의 댓글