정렬(Sorting)이란 데이터를 특정한 형식이나 규칙에 따라 체계적으로 배열하는 과정을 의미합니다. 정렬 알고리즘은 이러한 데이터를 특정 순서로 배치하는 구체적인 방법을 정의하며, 가장 널리 사용되는 순서는 수치 순서(numerical order)와 사전 순서(lexicographical order)입니다.
정렬이 중요한 이유는 데이터를 정렬된 상태로 저장해 두면 탐색(searching) 작업을 매우 효율적으로 최적화할 수 있기 때문입니다. 예를 들어, 정렬된 배열에서는 이진 탐색(Binary Search)처럼 빠른 검색 기법을 적용할 수 있습니다. 또한 정렬은 데이터를 사람이 읽기 쉬운 형태로 표현하는 데에도 폭넓게 활용됩니다.
이 섹션에서 다룰 주요 정렬 알고리즘
- 버블 정렬(Bubble Sort) − 인접한 두 요소를 반복적으로 비교·교환하며 정렬하는 가장 기본적인 기법
- 버킷 정렬(Bucket Sort) − 데이터를 여러 버킷으로 분배한 뒤 각각을 정렬하여 합치는 방식
- 콤 정렬(Comb Sort) − 버블 정렬을 개선하여 큰 간격부터 비교해 거북이 값(turtle value) 문제를 해결
- 계수 정렬(Counting Sort) − 각 값의 등장 횟수를 세어 정렬하는 비교 기반 아닌 알고리즘
- 사이클 정렬(Cycle Sort) − 쓰기 연산을 최소화하는 것이 특징인 이론적 최적 정렬
- 힙 정렬(Heap Sort) − 힙 자료구조를 활용해 O(n log n) 시간에 정렬을 보장
- 삽입 정렬(Insertion Sort) − 각 요소를 이미 정렬된 부분에 적절히 삽입하며 정렬
- 병합 정렬(Merge Sort) − 분할 정복(Divide and Conquer) 전략으로 안정적인 성능 제공
- 비둘기집 정렬(Pigeonhole Sort) − 값의 범위가 좁은 경우에 효율적인 분배 기반 정렬
- 퀵 정렬(Quick Sort) − 피벗(pivot)을 기준으로 분할하는 대표적인 고속 정렬 알고리즘
- 기수 정렬(Radix Sort) − 자릿수별로 안정 정렬을 반복 적용하는 비교 불필요 정렬
- 선택 정렬(Selection Sort) − 최솟값을 반복적으로 선택해 앞쪽에 배치하는 단순 정렬
- 셸 정렬(Shell Sort) − 삽입 정렬을 확장하여 간격(gap)을 줄여가며 정렬 효율을 높인 기법