빠른 비교
| 정렬 | 핵심 동작 | 시간 | 특징 |
|---|---|---|---|
| 버블 정렬 | 인접한 두 값을 계속 교환 | O(n²) | 구현은 단순하지만 실전 사용 적음 |
| 선택 정렬 | 남은 구간의 최솟값을 선택 | O(n²) | 교환 횟수가 적음 |
| 삽입 정렬 | 앞쪽의 정렬된 구간에 끼워 넣음 | O(n²) | 거의 정렬된 입력에 강함 |
구조
세 정렬은 모두 비교 기반 정렬이고, 평균적으로 O(n²)입니다. 입력이 조금만 커져도 n log n 정렬보다 불리하기 때문에 코딩 테스트에서 대량 데이터를 정렬할 때 직접 선택할 일은 거의 없습니다.
버블 정렬
버블 정렬은 인접한 두 값을 비교해서 순서가 틀리면 바꿉니다. 한 바퀴를 돌 때마다 가장 큰 값이 오른쪽 끝으로 밀려납니다.
csharp
for (int i = 0; i < arr.Length; i++)
{
for (int j = 0; j + 1 < arr.Length - i; j++)
{
if (arr[j] > arr[j + 1])
{
(arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
}
}
}선택 정렬
선택 정렬은 아직 정렬되지 않은 구간에서 최솟값을 찾아 맨 앞으로 보냅니다. 비교 횟수는 많지만 교환은 한 바퀴에 한 번입니다.
csharp
for (int i = 0; i < arr.Length; i++)
{
int minIndex = i;
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] < arr[minIndex]) minIndex = j;
}
(arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
}삽입 정렬
삽입 정렬은 앞쪽을 이미 정렬된 구간으로 보고, 새 값을 알맞은 위치에 끼워 넣습니다. 입력이 거의 정렬되어 있으면 이동이 적어서 빠르게 끝날 수 있습니다.
csharp
for (int i = 1; i < arr.Length; i++)
{
int value = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > value)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = value;
}선택 기준
| 상황 | 판단 |
|---|---|
| 정렬 개념 학습 | 세 정렬 모두 유용 |
| 입력이 매우 작음 | 구현 단순성을 우선할 수 있음 |
| 거의 정렬된 데이터 | 삽입 정렬 검토 |
| 교환 비용이 큼 | 선택 정렬의 적은 교환 횟수 참고 |
| 일반 코테 정렬 | Array.Sort, List.Sort 우선 |
정렬 문제에서 직접 구현이 목적이 아니라면 O(n²) 정렬보다 표준 정렬 API를 쓰는 편이 안전합니다.
주의할 점
n = 100,000에서 O(n²)은 거의 불가능합니다. 기본 정렬을 직접 구현해 제출하기 전에는 입력 크기를 먼저 확인하세요.
또 “정렬되어 있으면 빠르다”는 설명은 삽입 정렬이나 최적화된 버블 정렬에 해당합니다. 선택 정렬은 이미 정렬된 입력이어도 최솟값 탐색을 계속하므로 O(n²)입니다.
참고 링크
1 sources