42cursus/Push_swap at master · kimminkyeu/42cursus
이 글에선 5기 seseo
님이 고안하신 Merge Sort 접근법과, 이를 통해 제 과제에 병합정렬을 적용한 과정을 소개합니다.
100개 정렬
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>
: 삼각형들이 어떤 모양으로 있어야 병합하기 좋은가?
1개의 정렬될 집합을 정렬된 3개의 부분집합으로 분할(예측) 할 수 있습니다. 그리고 이렇게 정렬된 부분 집합은 삼각형의 모양입니다.
각 Stack의 Top과 Bottom에 있는 원소중 3개를 선택하여 비교합니다.