정렬

정렬은 이분 탐색, 그리디, 투 포인터 등 수많은 알고리즘의 전처리 단계이자, 시간 복잡도를 비교하며 알고리즘을 익히기 좋은 출발점이다. 실전에서는 대부분 언어 내장 정렬(O(n log n))을 쓰지만, 각 정렬의 원리를 알면 문제에 맞는 변형을 떠올리기 쉽다.

• 기본 정렬: 버블·선택·삽입·셸·계수·기수 정렬: 버블, 선택, 삽입 정렬(O(n²)), 간격을 줄여 가며 삽입 정렬하는 셸 정렬, 계수 정렬(O(n + k)), 기수 정렬(LSD·MSD)
• 병합 정렬과 퀵 정렬: 분할 정복을 쓰는 병합 정렬과 퀵 정렬, 정렬 알고리즘 비교
• 병합 삽입 정렬 (Ford-Johnson): 비교 횟수를 최소화하는 정렬, 야콥스탈 수 순서의 이진 삽입