push_swap

이번 과제에서는 스택에 있는 데이터를 한정된 명령어를 이용하여 최대한 적은 횟수 내에 정렬하는 것을 목표로 합니다. 성공하기 위해서는 다양한 정렬 알고리즘을 조작해 보고, 최적화된 데이터 정렬에 가장 적합한 알고리즘을 선택하여야 합니다.

명령어

우선 적기 편하게

5
4
3
2
1

이란 스택을 1 2 3 4 5로 표현한다면

swap: 1 2 3 5 4
push: 1 2 3 4
rotate: 5 1 2 3 4
reverse rotate: 2 3 4 5 1

으로 명령어가 진행이 됨

코드 흐름

1. parse_argument

인자는
./push_swap 2 1 3 5 4 이런식으로 들어오거나
./push_swap '2 1 3 5 4' 이런식으로 들어오거나
./push_swap '2 1 3' 5 '4' 이런식으로 들어올 수 있음.

따라서 split과 atoi를 통해서 인자를 스택에 입력해야함.

우선 atoi를 변형한 함수 append_data() 함수를 사용해서 잘못된 인자가 들어왔을 때의 에러처리와 스택에 입력을 동시에 진행함. 그리고 check_duplicate() 함수를 사용해서 중복된 인자가 입력되었을 때의 에러처리 또한 진행함.

그리고 스택을 사용해 2 1 3 5 4 라는 인자를 입력하면
2 1 3 5 4 그대로 스택에 저장되는데 위의 인자를 입력했을 때 과제가 원하는 바는

2
1
3
5
4

처럼 스택이 존재해야 함. 따라서 swap_stack() 함수를 사용하여 4 5 3 1 2 형태로 반전시켜줌

2. 정렬과 하드코딩

check_sorted() 함수를 사용하여 정렬되어 있다면 프로그램을 종료하고 정렬되지 않았다면 스택의 크기에 따른 최적화를 진행해줌

스택의 크기가 3일 때의 하드코딩

스택의 크기가 5일 때의 하드코딩

3. 스택의 분할

빠른 정렬을 위해서 스택을 3개의 요소로 분할하여 정렬할 것

우선 스택을 아무 정렬 알고리즘을 통해 정렬을 한 배열을 만들어 3등분을 시켜주는 최적의 피봇을 찾는다. 그리고 해당 피봇들을 기점으로 스택을 3등분 하여 두 피봇보다 큰 값은 그대로 a에 두고, 첫 피봇보다 작은 값은 b로 옮겨서 아래로 내리고, 중간에 위치하는 값들은 그대로 b로 옮긴다. 그리고 a에 3개의 요소만 남을 때 까지 b로 push해주면 스택 b에는 크기에 맞게 3등분된 덩어리들이 존재하게 된다.

4. 그리디

a는 sort_three() 함수를 사용하여 정렬해주고 남은 b에 있는 요소들을 a로 옮길 때 각 b의 인덱스가 a의 어디에 들어갈지 판단하여 가장 적은 명령어를 사용하여 위치할 수 있도록 한다. 만약 위치해야 하는 인덱스가 스택의 절반보다 작다면 rotate 명령어를 사용해 해당 위치를 top으로 올려주고, 위치해야 하는 인덱스가 스택의 절반보다 크다면 rrotate 명령어를 사용해 해당 위치를 top으로 만들어준다. 그러면 바로 push a 하면 끝, 해당 방법으로 모든 b의 요소를 a로 옮겨주면 아래의 그림처럼 변한다.

5. Last Rotate

위의 모습이 정렬이 모두 끝났다고 보기는 어렵기 때문에 기준점을 찾아주고 해당 기준점을 기준으로 rotate or rrotate로 정렬을 마무리 해준다.

Bonus

파싱까지의 과정은 동일하고 파싱을 한 뒤, push_swap에서 뱉어내는 명령어들을 모두 가져온 다음에 파싱한 인자들을 해당 명령어에 맞게 정렬하고, 마지막에 정렬이 되어있다면 OK를 출력, 그렇지 않다면 KO를 출력하도록 한다.