[push_swap] 정렬에 대한 공부 / 42 SEOUL

push_swap

 

Global variables are forbidden. (전역 변수 금지)

Segmentation fault, bus error, double free, etc (오류 발생이 되지 않도록 조치)

 

Game rules

The game is composed of 2 stacks named a and b

a는 서로 중복되지 않는 음수 혹은 양수인 난수들을 포함하고 b는 비어있다.

The goal is to sort in ascending order numbers into stack a

 

sa : swap a - 스택 a의 가장 위에 있는 두 원소(혹은 첫 번쨰 원소와 두 번째 원소)의 위치를 서로 바꾼다.

sb : swap b - 스택 b의 가장 위에 있는 두 원소(혹은 첫 번쨰 원소와 두 번째 원소)의 위치를 서로 바꾼다.

ss : sa와 sb를 동시에 실행한다.

pa : push a - 스택 b에서 가장 위(탑)에 있는 원소를 가져와서, 스택 a의 맨 위(탑)에 넣는다. 스택 b가 비어 있으면 아무 것도 하지 않는다.

pb : push b - 스택 a에서 가장 위(탑)에 있는 원소를 가져와서, 스택 b의 맨 위(탑)에 넣는다. 스택 a가 비어있으면 아무 것도 하지 않는다.

ra : rotate a - 스택 a의 모든 원소들을 위로 1 인덱스 만큼 올린다. 첫 번째 원소(탑)는 마지막 원소(바텀)가 된다.

rb : rotate b - 스택 b의 모든 원소들을 위로 1 인덱스 만큼 올린다. 첫 번째 원소(탑)는 마지막 원소(바텀)가 된다.

rr : ra와 rb를 동시에 실행한다.

rra : reverse rotate a - 스택 a의 모든 원소들을 아래로 1 인덱스 만큼 내린다. 마지막 원소(바텀)는 첫 번째 원소(탑)가 된다.

rrb : reverse rotate b - 스택 b의 모든 원소들을 아래로 1 인덱스 만큼 내린다. 마지막 원소(바텀)는 첫 번째 원소(탑)가 된다.

rrr : rra와 rrb를 동시에 실행한다.

 

"push_swap" 프로그램 ▶ 이 프로그램은 스택 a에 들어갈 값들을 정수 리스트의 형태로 포맷팅하여 인자로 받는다. ▶ 첫 번째 인자는 스택의 탑이 된다(순서에 유의해라). ▶ 프로그램은 반드시 스택 a를 정렬하는데 가능한 가장 작은 개수의 명령어 리스트를 출력해야 한다. ▶ 명령어들은 '\n'으로만 구분되어야 한다. ▶ 목표는 가능한 적은 개수의 명령어 집합으로 스택을 정렬하는 것이다. 평가 도중에는 프로그램에서 도출한 명령어의 수와 허용된 최대 작업수를 비교한다. 프로그램에 너무 큰 리스트가 표시되거나 목록이 제대로 정렬되지 않은 경우 점수를 얻지 못한다. ▶ 에러의 경우에는, Error와 줄바꿈을 표준 에러에 출력해야 한다. 에러는 다음 예시들을 포함한다: 일부 인자가 정수가 아니거나, 정수 범위를 초과하거나, 중복이 있는 경우이다.

정렬을 위한 확인 작업

 

A기준에서 우선적으로 해야할 것들

pb : head->index < 중위값 sa : head->next->index - head->index == 1 head->next->next->index - head->index == 1 (Top에서 2번째, 3번째와 비교했을 때, 인덱스 값 차이가 -1이라면 swap) rra : head->index - tail->index == 1 head->index - tail->prev->index == 1 (Top에서 Bottom 혹은 그보다 앞에 있는 값을 비교했을 때, 인덱스 값 차이가 1이라면 reverse_rotate) else ra

B 기준에서 무엇을 체크해야 하는 지

pb : A정렬이 된 상태 & A->head->index - B->head->index == 1 sb : head->index - head->next->index == 1 head->index - head->next->next->index == 1 (B에서는 내림차순으로 정렬이기 때문에, A와는 반대로 적용) rrb : tail->index - head->index == 1  tail->prev->index - head->index == 1

 

---

아래의 글을 참고

https://www.notion.so/push_swap-c15e62229b9541d78fadec4d6aae8b50

 

https://www.geeksforgeeks.org/improvement-on-the-quick-sort-algorithm/

Improvement on the Quick Sort Algorithm - GeeksforGeeks

 

https://algs4.cs.princeton.edu/23quicksort/

Quicksort

 

https://www.techiedelight.com/hybrid-quicksort/

Hybrid QuickSort Algorithm | Techie Delight