정렬 알고리즘은 데이터를 특정 기준에 따라 나열하는 프로그래밍의 기초다.
각 알고리즘의 시간 복잡도와 공간 복잡도를 이해하고 상황에 맞는 방식을 선택하는 것이 중요하다.
퀵 정렬 (Quick Sort)
분할 정복(Divide and Conquer) 방식을 사용하는 고속 정렬 알고리즘이다.
피벗(Pivot)을 기준으로 작은 값과 큰 값을 나누어 재귀적으로 정렬한다.
void quickSort(int arr[], int left, int right) {
if (left >= right) return;
int pivot = arr[(left + right) / 2];
int i = left, j = right;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
std::swap(arr[i], arr[j]);
i++; j--;
}
}
quickSort(arr, left, j);
quickSort(arr, i, right);
}
병합 정렬 (Merge Sort)
데이터를 최소 단위까지 분할한 뒤, 정렬하면서 다시 합치는 방식이다.
항상 일정한 성능을 보장하며 안정 정렬(Stable Sort)이라는 특징이 있다.
void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void merge(int[] arr, int l, int m, int r) {
// 두 부분 배열을 정렬된 상태로 합치는 로직 (추가 메모리 필요)
}
알고리즘 성능 비교
| 알고리즘 | 평균 시간 복잡도 | 최악 시간 복잡도 | 공간 복잡도 | 특징 |
| :— | :— | :— | :— | :— |
| 버블 정렬 | O(N^2) | O(N^2) | O(1) | 구현이 매우 단순함 |
| 삽입 정렬 | O(N^2) | O(N^2) | O(1) | 거의 정렬된 상태에서 매우 빠름 |
| 퀵 정렬 | O(N log N) | O(N^2) | O(log N) | 실제 성능이 가장 우수함 |
| 병합 정렬 | O(N log N) | O(N log N) | O(N) | 일정한 성능 보장, 추가 메모리 필요 |
P.S
일반적인 상황에서는 퀵 정렬이 가장 효율적이지만, 데이터의 정렬 상태나 메모리 제약, 안정성 필요 여부에 따라 적절한 알고리즘을 선택해야 한다.
현대 언어의 표준 라이브러리 정렬 함수들은 대개 이 알고리즘들을 혼합한 하이브리드 방식(Timsort, Introsort 등)을 사용하는 것 같다.
