[push_swap] 4. 정렬 알고리즘

본 과제를 해결하기 위해서는 반드시 문제에 제시된 스택과 스택의 연산을 사용하여 들어온 숫자들을 정렬해야 한다.

 

단, 통과를 위해서는 일정 횟수 이하로 스택의 정렬을 끝마쳐야 하며 이를 달성하기 위해선 사용하는 알고리즘이 적어도 n log(n)의 시간복잡도를 만족해야 한다...

출처 : https://www.bigocheatsheet.com/

나는 처음에 

'ㅋ 껌~이~지~ 이거 그냥 퀵소트로 정렬하면 되는 것 아님?'

이라고 생각한 후 적당히 피벗을 잡아 A스택과 B스택을 와리가리하며 정렬을 완료하는 알고리즘을 구현했다.

결과는 대참사였다. 정수 100개 정렬에 대략 1200회, 500개 정렬에는 대략 10000회가 걸리는 알고리즘이 탄생했고 과제 통과에는 턱없이 부족한 숫자였다.

 

대략 패닉에 빠져 어떡하지를 외치다가 어떤 분의 소개로 42서울 push_swap의 바이블, minckim님의 push_swap 가이드에서 구원을 찾을 수 있었다.

 

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

push_swap 가이드

 

아이디어는 기존의 퀵정렬에서 피봇을 하나 더 추가하여 A스택에 넘기는 숫자들에 대해서도 두 그룹으로 나누어 보내는 것이었다.

 

요로코롬 나눠주면 B스택에 숫자들이 쌓일 때 한 층 더 정렬된 형태로 쌓이기 때문에 스택이 의미없이 회전하는 횟수가 적어진다.

 

요 알고리즘을 적용하고 나니 대략 100개 정렬에 900회, 500개 정렬에 7000회 정도로 그래도 어찌저찌 최적화를 하면 통과가 가능한 수준으로 명령어 횟수가 감소하였다.

 

이제 남은 것은 지옥의 최적화...