[알고리즘] 정렬 (Sort) - 거품, 선택, 삽입, 퀵, 병합 정렬 정리 (Java)
정렬의 방법은 여러 가지가 있다.
그중 대표적인 정렬인 거품, 선택, 삽입, 퀵, 병합 정렬을 자바로 구현해보고
시간복잡도와 장단점을 가볍게 정리해보려고 한다.
1️⃣ 거품 정렬 (Bubble Sort)
인접한 두 원소의 대소를 비교, 조건에 따라 (오름차순 or 내림차순) 교환하여 가장 뒤로 하나씩 보내는 방식
static void bubbleSort(int[] arr){
int size = arr.length;
for(int i = size; i > 0; i--){
for(int j = 1; j < i; j++){
// swap
if(arr[j - 1] > arr[j]) {
int tmp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = tmp;
}
}
}
}시간 복잡도
- 최선 : O(n^2)
- 최악 : O(n^2)
- 평균 : O(n^2)
2중 반복문이므로 모든 시간 복잡도가 n^2이다.
장점
- 안정 정렬 (정렬 전 후 순서 보장)
- 다른 메모리 공간을 필요로 하지 않음
단점
- 최선, 최악, 평균 시간 복잡도가 O(n^2) 비효율적
2️⃣ 선택 정렬 (Selection Sort)
첫 번째 위치 원소를 선택, 두 번째 원소부터 끝까지 비교하여 가장 작은 값을 첫 번째 위치와 교환
두 번째 위치 원소를 선택, 세 번째 원소부터 끝까지 비교하여 가장 작은 값을 두 번째 위치와 교환하는 과정을 반복하여 정렬하는 방식
static void selectionSort(int[] arr){
int size = arr.length;
for(int i = 0; i < size; i++){
int index = i;
for(int j = i + 1; j < size; j++){
if(arr[j] < arr[index]){
index = j;
}
}
// swap
int tmp = arr[index];
arr[index] = arr[i];
arr[i] = tmp;
}
}시간 복잡도
- 최선 : O(n^2)
- 최악 : O(n^2)
- 평균 : O(n^2)
2중 반복문이므로 모든 시간 복잡도가 n^2이다.
장점
- 다른 메모리 공간을 필요로 하지 않음
단점
- 최선, 최악, 평균 시간 복잡도가 O(n^2) 비효율적
- 불안정 정렬 (정렬 전 후 순서 보장 X)
3️⃣ 삽입 정렬 (Insertion Sort)
두 번째 원소부터 시작, 앞쪽의 원소들과 대소를 비교하여 삽입할 위치를 지정한 뒤, 원소를 뒤로 옮겨 삽입 위치에 자료를 삽입하는 방식
static void insertionSort(int[] arr){
int size = arr.length;
for(int i = 1; i < size; i++){
int tmp = arr[i];
int prev = i - 1;
while(prev >= 0 && arr[prev] > tmp){
arr[prev + 1] = arr[prev];
prev--;
}
arr[prev + 1] = tmp;
}
}시간 복잡도
- 최선 : O(n)
- 최악 : O(n^2)
- 평균 : O(n^2)
2중 반복문이므로 평균, 최악의 경우 시간 복잡도가 n^2이다.
하지만 이미 정렬되어 있는 배열의 경우 한 번씩 비교하면 끝나게 되므로 최선의 경우 O(n)이다.
장점
- 다른 메모리 공간을 필요로 하지 않음
- 거의 정렬되어 있는 배열에서 효율적
- 안정 정렬
단점
- 최악, 평균 시간 복잡도가 O(n^2) 비효율적
4️⃣ 퀵 정렬 (Quick Sort)
하나의 기준점(Pivot)을 잡고 Pivot의 앞에는 그보다 작은 원소들로, Pivot의 뒤에는 그보다 큰 원들이 오도록 교환하여 두 개의 리스트로 분할 후 그 분할된 리스트에 계속 반복하여 정리하는 방식
static void quickSort(int[] arr, int left, int right){
if(left >= right) return;
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left, j = right;
while(i < j) {
while(i < j && pivot < arr[j]) {
j--;
}
while(i < j && pivot >= arr[i]){
i++;
}
// swap
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
arr[left] = arr[i];
arr[i] = pivot;
return i;
}
시간 복잡도
- 최선 : O(nlog₂n)
- 최악 : O(n^2)
- 평균 : O(nlog₂n)
분할 정복 방식을 통해 진행하므로 반복 횟수는 log₂n ,
반복 단계에서 모든 원소를 탐색하므로 n 번의 연산이 이루어진다.
때문에 평균적으로 O(nlog₂n),
이미 정렬되어 있는 배열의 경우 불균형 분할이 발생하여 O(n^2)의 시간 복잡도를 가진다.
장점
- 결정된 피벗들은 연산에서 제외되기 때문에 O(nlog₂n)의 시간복잡도를 가지는 다른 정렬보다 효율적
단점
- 불안정 정렬
- 정렬된 배열에서는 분할의 불균형으로 인해 O(n^2)의 시간복잡도를 가짐
- 반복 호출로 인해 평균 O(log₂n)의 메모리 공간 필요함
5️⃣ 병합 정렬 (Merge Sort)
하나의 배열을 두 개의 균등한 크기로 분할 후 그 부분 배열들을 정렬, 다시 결합하여 정렬하는 방식
static 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);
}
}
static void merge(int[] arr, int left, int mid, int right) {
int[] L = Arrays.copyOfRange(arr, left, mid + 1);
int[] R = Arrays.copyOfRange(arr, mid + 1, right + 1);
int i = 0, j = 0, k = left;
int ll = L.length, rl = R.length;
while (i < ll && j < rl) {
if (L[i] <= R[j]) {
arr[k] = L[i++];
} else {
arr[k] = R[j++];
}
k++;
}
while (i < ll) {
arr[k++] = L[i++];
}
while (j < rl) {
arr[k++] = R[j++];
}
}
시간 복잡도
- 최선 : O(nlog₂n)
- 최악 : O(nlog₂n)
- 평균 : O(nlog₂n)
항상 두 부분으로 분할하는 과정을 통해 O(nlog₂n)의 시간 복잡도를 가진다.
또한 병합의 대상이 되는 두 배열이 이미 정렬되어 있으므로 순차 비교를 통해 정렬 가능하다.
따라서 LinkedList를 정렬할 때 효율적이다.
장점
- 안정 정렬
- O(nlog₂n)의 시간 복잡도
- LinkedList 정렬 효율적
단점
- 부분 정렬한 값들 저장할 O(n)의 메모리 공간 필요
정리
| 정렬 종류 | 시간복잡도 | ||
| 최선 | 최악 | 평균 | |
| 거품 정렬 | O(n^2) | O(n^2) | O(n^2) |
| 선택 정렬 | O(n^2) | O(n^2) | O(n^2) |
| 삽입 정렬 | O(n) | O(n^2) | O(n^2) |
| 퀵 정렬 | O(nlog₂n) | O(n^2) | O(nlog₂n) |
| 병합 정렬 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) |
