🎮 이 단원이 게임에서 쓰이는 곳 (언더테일·RPG)
퀵·병합·힙 정렬 = 아이템이 수백·수천 개일 때 인벤토리 정렬을 빠르게 하려면 이런 고급 정렬을 씁니다. 게임 엔진 내부에서는 보통 라이브러리 정렬(sort)을 쓰고, 그 안에서 퀵/병합/힙이 조합돼요. 개념만 알아두면 "왜 정렬이 O(n log n)까지 줄어드는지" 이해하는 데 도움이 됩니다.
더 빠른 정렬 (참고)
버블·선택·삽입은 이해하기 쉽지만 데이터가 많으면 느려요. 아래는 더 빠른 방법이에요. 이름만 알아 두어도 돼요.
퀵 정렬(Quick Sort, 퀵 소트)
기준값(pivot, 피벗)을 하나 잡고, 그보다 작은 것 / 큰 것을 나눠서 각각 정렬한 뒤 합쳐요. 평균적으로 빠르지만, 최악의 경우엔 느릴 수 있어요.
병합 정렬(Merge Sort, 머지 소트)
반으로 나눠서 각각 정렬한 다음, 합치면서 순서를 맞춰요. 항상 같은 속도로 동작하고, 안정 정렬이에요.
힙 정렬(Heap Sort, 힙 소트)
"힙(heap, 힙)"이라는 특별한 트리 구조를 이용해서, 가장 큰 값(또는 작은 값)을 차례로 꺼내며 정렬해요.
프로그래밍기능사에서는 버블·선택·삽입의 한 단계 결과를 묻는 문제가 많아요. 위 세 가지(퀵·병합·힙)는 이름과 아이디어만 알면 됩니다. 정렬 코드 실습은 2. 버블·선택·삽입에서 해요.