정렬 알고리즘은 과거부터 현재까지 컴퓨터 과학자들에 의해 계속해서 연구되어지고 있다.
그 과정에서 수많은 정렬 알고리즘이 생겨났고, 그 중 가장 자주 쓰이고 알려져 있는 알고리즘에는 버블 정렬(거품 정렬), 삽입 정렬, 선택 정렬, 퀵 정렬, 병합 정렬 등이 있다.
이번 포스팅에서는 정렬들에 대해 자세히 알아보려고 한다.
정렬이 중요한 이유
선형 자료구조는 데이터를 한 줄로 나열하기 때문에 일정한 규칙에 맞게 재배치하는 것이 중요하다.
더 효율적인 알고리즘을 사용하기 위해 정렬을 사용하는 것이다.
정렬의 종류
- 버블정렬
- 가장 무식하게 정렬하는 방법
- 시간복잡도 : O(n^2)
맨 앞부터 시작, 인접한 값과 비교하며 큰 값은 뒤로, 작은 값은 앞으로 보낸다.
과정을 마치고 나면 맨 뒤에는 가장 큰 값이 위치하게 된다.
뒤쪽의 정렬된 값을 제외하고, 나머지에 대해 같은 과정을 반복해 전체 배열에 대한 정렬을 수행.`
public class Sorts {
static void bubbleSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
}
}
}
}
static void swap(int a[] , int i, int j){
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}- 삽입 정렬
-
이미 정렬되어있는 배열에서 데이터를 적당한 위치에 끼워넣는 것
-
시간복잡도 : O(n^2), 배열이 이미 정렬된 경우 O(n)
두번째부터 마지막 값까지 차례로 아래 규칙에 따라 정렬 시작
정렬 대상과 대상의 왼쪽 원소와 비교해 왼쪽 원소가 크다면 위치를 교환한다.
반복하다가 왼쪽 원소가 크지 않은 경우 해당 자리가 정렬 대상 원소가 들어갈 자리가 된다.
-
구현
public class Sorts {
static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int target = a[i];
int j = i - 1;
while (j >= 0 && tmp < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = tmp;
}
}
}- 선택 정렬
- 가장 단순한 형태의 정렬
- 시간복잡도 : O(n^2)
맨 앞부터 차례대로 정렬할 대상 인덱스로 설정한다.
원소들 중 가장 작은 데이터를 선택해 정렬 대상 인덱스와 Swap(교환)한다.
정렬된 인덱스의 다음 인덱스를 대상 인덱스로 설정해 과정을 반복한다.
- 구현
public class Sorts {
static void selectionSort(int[] a) {
int n = a.length;
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[min]) min = j;
}
swap(a, i, min);
}
}
static void swap(int a[] , int i, int j){
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}- 퀵 정렬
- 평균적인 상황에서 가장 좋은 성능을 가지는 정렬
- 고정값 pivot을 설정
- 분할 정복법의 알고리즘 사용
- 시간복잡도 : O(n log n), 최악의 경우 O(n^2)
분할(Divide): 배열에서 하나의 요소를 선택해 pivot으로 설정한다.
pivot을 기준으로 pivot보다 작은 요소는 pivot의 왼쪽으로, 큰 요소는 오른쪽으로 이동.
정복(Conquer): pivot을 기준으로 분할된 두 개의 부분 배열에 대해 재귀적으로 퀵 정렬을 수행한다. (부분 배열의 크기≤1 일 때 까지 반복)
결합(Combine): 모든 정렬된 부분 배열을 결합하여 최종적으로 정렬된 배열을 얻는다.
- 구현
public class Sorts {
static void sort(int[] a) {
quickSort(a, 0, a.length - 1);
}
static void quickSort(int[] a, int left, int right) {
int p = partition(a, left, right);
if (left < p - 1) quickSort(a, left, p - 1);
if (p < right) quickSort(a, p + 1, right);
}
static int partition(int[] a, int left, int right) {
int pivot = arr[(left + right) / 2];
while (left <= right) {
while (arr[left] < pivot) {
left++;
}
while (arr[right] > pivot) {
right--;
}
if (left <= right) {
swap(arr, left, right);
left++;
right--;
}
}
return left;
}
}
left: 부분 배열의 첫 인덱스 ,right: 부분 배열의 마지막 인덱스
pivot= 그 중간의 원소값 사용partition() : left의 원소 값이 pivot보다 클 때까지 증가시키면서 찾고, right의 원소 값이 pivot보다 작을 때까지 감소시키면서 찾는다. 찾은 후 두 원소를 교환한다.
반복하다 보면 자연스럽게 pivot의 왼쪽에는 pivot 보다 작은 값들이 정렬되고 오른쪽에는 더 큰 값들이 위치하게 된다.
pivot의 위치인 left를 반환→ 다시 해당 pivot을 기준으로 좌측, 우측 부분집합으로 나누어 재귀 호출 한다.
-
병합 정렬
- 배열을 반으로 분할해 각각 정렬한 뒤, 두 정렬 배열을 병합하는 정렬
- 분할 정복법 알고리즘 사용
- 시간복잡도 : O(n log n)
분할(Divide): 배열을 두 개의 같은 크기로 분할한다. 재귀적으로 수행되며 더 이상 분할할 수 없을 때까지 반복한다.
정복(Conquer): 분할된 각 부분에 대해 재귀적으로 합병 정렬을 통해 배열을 정렬한다.
병합(Combine): 정렬된 두 개의 부분 배열을 병합하여 하나의 정렬된 배열로 만든다.
public class Sorts {
static void sort(int[] a) {
int[] tmp = new int[a.length];
mergeSort(a, tmp, 0, a.length - 1);
}
static void mergeSort(int[] a, int[] tmp, int left, int right) {
if (left >= right) return;
int mid = lo + (right - left) / 2;
mergeSort(a, tmp, left, mid);
mergeSort(a, tmp, mid + 1, right);
merge(a, tmp, left, mid, right);
}
static void merge(int[] a, int[] tmp, int left, int mid, int right) {
int i = left, j = mid + 1, k = right;
while (i <= mid && j <= right) {
if (a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= hight) tmp[k++] = a[j++];
for (int t = left; t <= right; t++) a[t] = tmp[t];
}
}정리
| 알고리즘 | 평균 시간 | 최악 시간 | 안정성 | 비고/언제 쓰나 |
|---|---|---|---|---|
| 선택 정렬 | O(n²) | O(n²) | 불안정 | 교환 횟수 적음(쓰기 비용 큰 매체에 드물게) |
| 버블 정렬 | O(n²) | O(n²) | 안정 | 교육용/거의 정렬된 데이터에서 조기 종료 |
| 삽입 정렬 | O(n²) | O(n²) | 안정 | 작은 n 또는 거의 정렬된 배열에 매우 강함 |
| 퀵 정렬 | O(n log n) | O(n²) | 불안정 | 평균 성능 매우 우수, 피벗 선택 중요 |
| 병합 정렬 | O(n log n) | O(n log n) | 안정 | 외부정렬, 연결리스트, 안정성 필수일 때 |
