정렬
기술노트
정렬
정렬 알고리즘은 데이터 요소를 특정 순서(일반적으로 오름차순 또는 내림차순)로 배열하는 알고리즘입니다. 이는 컴퓨터 과학에서 가장 기본적이고 중요한 문제 중 하나로, 다양한 응용 프로그램에서 폭넓게 사용됩니다.
주요 정렬 알고리즘
버블 정렬(Bubble Sort)
- 개념: 인접한 두 원소를 비교하여 필요시 교환하는 과정을 반복하는 간단한 정렬 알고리즘
- 작동 방식:
- 배열을 순회하며 인접한 두 원소를 비교
- 왼쪽 원소가 오른쪽 원소보다 크면 두 원소 교환
- 배열의 끝까지 도달하면 가장 큰 원소가 맨 오른쪽에 위치
- 이 과정을 배열이 정렬될 때까지 반복
- 시간복잡도: O(n²)
- 공간복잡도: O(1)
- 특징: 안정적인 정렬 알고리즘, 구현이 간단, 작은 데이터셋에 적합
void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// 교환
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
선택 정렬(Selection Sort)
- 개념: 현재 위치에 들어갈 값을 찾아 교환하는 정렬 알고리즘
- 작동 방식:
- 정렬되지 않은 부분에서 최소값(또는 최대값) 찾기
- 이 값을 정렬되지 않은 부분의 첫 번째 원소와 교환
- 정렬된 부분을 한 원소씩 늘려가며 전체가 정렬될 때까지 반복
- 시간복잡도: O(n²)
- 공간복잡도: O(1)
- 특징: 불안정 정렬 알고리즘, 교환 횟수가 적음, 작은 데이터셋에 적합
void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 최소값을 현재 위치와 교환
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
삽입 정렬(Insertion Sort)
- 개념: 현재 값을 이미 정렬된 부분의 적절한 위치에 삽입하는 정렬 알고리즘
- 작동 방식:
- 두 번째 원소부터 시작하여 이전 원소들과 비교
- 자신의 위치를 찾을 때까지 이전 원소들을 뒤로 이동
- 적절한 위치에 현재 원소 삽입
- 배열의 끝까지 이 과정 반복
- 시간복잡도: 평균/최악 O(n²), 최선 O(n)
- 공간복잡도: O(1)
- 특징: 안정적인 정렬 알고리즘, 작은 데이터셋이나 거의 정렬된 데이터에 효율적
void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// key보다 큰 원소들을 뒤로 이동
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
병합 정렬(Merge Sort)
- 개념: 분할 정복 방식을 사용하는 정렬 알고리즘
- 작동 방식:
- 배열을 절반으로 분할(Divide)
- 각 부분 배열을 재귀적으로 정렬(Conquer)
- 정렬된 부분 배열을 병합(Merge)
- 시간복잡도: O(n log n)
- 공간복잡도: O(n)
- 특징: 안정적인 정렬 알고리즘, 대용량 데이터 처리에 효율적, 추가 메모리 필요
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 left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// 임시 배열 생성
int[] L = new int[n1];
int[] R = new int[n2];
// 데이터 복사
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// 병합
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 남은 요소 복사
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
퀵 정렬(Quick Sort)
- 개념: 분할 정복 방식을 사용하는 정렬 알고리즘으로, 피벗을 기준으로 배열 분할
- 작동 방식:
- 배열에서 피벗(pivot) 원소 선택
- 피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 분할(Partition)
- 분할된 부분 배열에 대해 재귀적으로 퀵 정렬 적용
- 시간복잡도: 평균 O(n log n), 최악 O(n²)
- 공간복잡도: O(log n)
- 특징: 불안정 정렬 알고리즘, 실제 구현에서 매우 빠른 성능, 피벗 선택이 중요
void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 분할 위치
int pivotIndex = partition(arr, low, high);
// 분할된 부분 배열 정렬
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
// 교환
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 피벗 위치 교환
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
힙 정렬(Heap Sort)
- 개념: 힙 자료구조를 이용한 정렬 알고리즘
- 작동 방식:
- 배열을 최대 힙(Max Heap)으로 구성
- 루트(최대값)를 배열의 맨 끝 원소와 교환
- 힙 크기를 줄이고 새 루트를 힙 속성을 만족하도록 조정(heapify)
- 힙이 비어질 때까지 2-3 단계 반복
- 시간복잡도: O(n log n)
- 공간복잡도: O(1)
- 특징: 불안정 정렬 알고리즘, 제자리 정렬(in-place), 대용량 데이터 처리에 적합
void heapSort(int[] arr) {
int n = arr.length;
// 최대 힙 구성
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 힙에서 원소를 하나씩 추출
for (int i = n - 1; i > 0; i--) {
// 현재 루트를 맨 끝으로 이동
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 줄어든 힙에 대해 heapify 호출
heapify(arr, i, 0);
}
}
void heapify(int[] arr, int n, int i) {
int largest = i; // 루트를 최대값으로 초기화
int left = 2 * i + 1;
int right = 2 * i + 2;
// 왼쪽 자식이 루트보다 크다면
if (left < n && arr[left] > arr[largest])
largest = left;
// 오른쪽 자식이 현재 최대값보다 크다면
if (right < n && arr[right] > arr[largest])
largest = right;
// 루트가 최대값이 아니라면
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 영향 받은 서브트리에 대해 재귀적으로 heapify
heapify(arr, n, largest);
}
}
정렬 알고리즘 비교
알고리즘 | 시간복잡도(최선) | 시간복잡도(평균) | 시간복잡도(최악) | 공간복잡도 | 안정성 |
---|---|---|---|---|---|
버블 정렬 | O(n) | O(n²) | O(n²) | O(1) | 안정 |
선택 정렬 | O(n²) | O(n²) | O(n²) | O(1) | 불안정 |
삽입 정렬 | O(n) | O(n²) | O(n²) | O(1) | 안정 |
병합 정렬 | O(n log n) | O(n log n) | O(n log n) | O(n) | 안정 |
퀵 정렬 | O(n log n) | O(n log n) | O(n²) | O(log n) | 불안정 |
힙 정렬 | O(n log n) | O(n log n) | O(n log n) | O(1) | 불안정 |
정렬 알고리즘 선택 기준
데이터셋 크기
- 작은 데이터셋: 삽입 정렬, 버블 정렬 등 간단한 알고리즘 적합
- 큰 데이터셋: 퀵 정렬, 병합 정렬, 힙 정렬 등 효율적인 알고리즘 필요
데이터 특성
- 거의 정렬된 데이터: 삽입 정렬이 효율적
- 무작위 데이터: 퀵 정렬이 일반적으로 좋은 성능
- 역순으로 정렬된 데이터: 퀵 정렬은 피벗 선택에 따라 최악의 성능, 병합 정렬이 적합
메모리 제약
- 메모리 제한적: 제자리 정렬(in-place)인 퀵 정렬, 힙 정렬 선호
- 추가 메모리 사용 가능: 병합 정렬 등 사용 가능
안정성 요구
- 안정성 필요: 병합 정렬, 삽입 정렬 선택
- 안정성 불필요: 퀵 정렬, 힙 정렬 사용 가능
고급 정렬 알고리즘
팀소트(Timsort)
- 파이썬과 자바의 기본 정렬 알고리즘
- 병합 정렬과 삽입 정렬을 결합한 하이브리드 알고리즘
- 실제 데이터에서 매우 효율적
카운팅 정렬(Counting Sort)
- 정수 정렬에 특화된 비교 기반이 아닌 정렬 알고리즘
- 시간복잡도: O(n + k) (k는 값의 범위)
- 제한된 범위의 정수 정렬에 매우 효율적
기수 정렬(Radix Sort)
- 낮은 자리 숫자부터 비교하여 정렬하는 비교 기반이 아닌 정렬 알고리즘
- 시간복잡도: O(d * (n + k)) (d는 최대 자릿수, k는 기수)
- 정수나 문자열 정렬에 효과적
셸 정렬(Shell Sort)
- 삽입 정렬의 개선 버전으로, 간격(gap)을 두고 부분 집합을 정렬 후 간격을 줄이는 방식
- 시간복잡도: 간격 시퀀스에 따라 다름(일반적으로 O(n log²n))
- 중간 크기의 배열에 효과적
정렬 알고리즘의 응용
- 데이터베이스: 쿼리 결과 정렬
- 검색 엔진: 검색 결과 랭킹
- 컴퓨터 그래픽: Z-버퍼링 등 깊이 정렬
- 데이터 분석: 통계 처리, 이상치 탐지
- 압축 알고리즘: 허프만 코딩 등에서 사용
- 네트워크 라우팅: 패킷 우선순위 결정