42cursus/Push_swap at master · kimminkyeu/42cursus

Push Swap using Merge Sort

이 글에선 5기 seseo 님이 고안하신 Merge Sort 접근법과, 이를 통해 제 과제에 병합정렬을 적용한 과정을 소개합니다.


100개 정렬

100개 정렬

500개 정렬

500개 정렬


⚠️ 같은 성능의 병합정렬이여도, 구현 로직이 다르면 위 영상과 정렬 과정이 달라집니다. “아 삼각형을 계속 합치는 구나~” 정도 감을 잡으시면 좋을 것 같습니다.


목차


◼️ 병합 정렬 평균 성능

<aside> 💡 $분할 \ O(n) ,\ 병합\ O(nlog_3n)$


1️⃣ 100개 정렬 : ra rb = rr와 같은 명령어 최적화 후 → 평균 620개

2️⃣ 500개 정렬 : ra rb = rr와 같은 명령어 최적화 후 → 평균 4480개

3️⃣ 1000개 정렬 : ra rb = rr와 같은 명령어 최적화 후 → 평균 9510개


🏖 입력값의 분포에 영향받지 않아 명령어 개수가 일정하게 나오는게 장점입니다.

</aside>


◼️ 접근 아이디어

: 삼각형들이 어떤 모양으로 있어야 병합하기 좋은가?

0️⃣  분할 : 삼각형 합치기 전 모양을 거꾸로 유추하기 (가정법)

1개의 정렬 집합을 정렬된 3개의 부분집합으로 분할(예측) 할 수 있습니다. 그리고 이렇게 정렬된 부분 집합은 삼각형의 모양입니다.


1️⃣  스택의 가장자리 원소들만 비교해서 삼각형(크기=3) 만들기

각 Stack의 Top과 Bottom에 있는 원소중 3개를 선택하여 비교합니다.