정렬
- 정렬 : 데이터의 집합을 어떠한 기준으로 일정한 순서로 줄지어 세우는 것.
정렬 알고리즘은 정말 많지만, 그중 가장 대표적인 정렬 알고리즘 5가지를 알아볼 것이다.
아래에 설명할 정렬 알고리즘은 모두 오름차순 정렬을 목표로 작성했다.
선택 정렬
- 작은 데이터를 선별하여 데이터를 앞으로 보내는 정렬 방식
public static void sort() {
for (int i = 0; i < arr.length - 1; i++) {
int idx = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[idx] > arr[j]) {
idx = j;
}
}
int tmp = arr[idx];
arr[idx] = arr[i];
arr[i] = tmp;
}
}- 선택 정렬은 작은 값을 우선적으로 정렬하는 알고리즘이다.
- 위의 코드를 보면 i = 0 일 때, idx = 0 으로 초기화 한 후, for문을 돌면서 계속 더 작은 값의 인덱스로 idx값을 갱신하는 것을 알 수 있다.
- for문을 돌린 후 idx의 값과 i의 값을 바꿔 i에 가장 작은 값을 넣는다.
- 그후 다시 i++를 통해 i값을 올리고 같은 로직을 수행하는데, arr.length - 2까지 for문을 돌린다.
-> 앞에서 부터 값을 1개 씩 설정하면, 가장 마지막 값은 자연스럽게 가장 큰 값이 오기 때문에 for문을 돌릴 필요가 없다.
시간복잡도
O(N^2)
(N-1)(회전1) + (N-2)(회전2) + .. + 2 + 1 -> N(N-1)/2 이므로 O(N^2)의 시간복잡도를 가진다.
버블 정렬
- 바로 앞에 있는 것과 비교해서 정렬하는 방식
public static void sort() {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length -1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
}
}
}
}- 바로 앞의 값과 계속 비교하면서 가장 큰 값을 가장 뒤로 하나씩 배치하는 정렬하는 알고리즘이다.
- 우선 선택 정렬과 동일하게 i 루프를 돌리는데, 큰 값을 계속 루프 1번마다 정렬하여, 가장 작은 값은 자연스럽게 정렬되기 때문이다.
- arr[j] > arr[j + 1] 를 보면 바로 앞의 값과 계속 비교해 앞의 값이 더 크면 서로 값을 바꾸는 것을 알 수 있다.
- 뒤쪽 부터 값이 정렬되기 때문에, j 루프의 경우 arr.length - 2 - i 까지 돌면 된다.
(-> 값이 뒤쪽 부터 1개씩 확정적으로 정렬되기 때문에)
시간복잡도
O(N^2)
(N-1)(회전1) + (N-2)(회전2) + .. + 2 + 1 -> N(N-1)/2 이므로 O(N^2)의 시간복잡도를 가진다.
삽입 정렬
- 앞에서 부터 차례대로 자신의 위치를 찾아 삽입하는 정렬 방식
public static void sort() {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > tmp) {
arr[j + 1] = arr[j];
if (j == 0) {
arr[0] = tmp;
}
} else {
arr[j + 1] = tmp;
break;
}
}
}
}- 자신의 인덱스부터 0까지의 값을 정렬하면서 자신의 인덱스를 찾아 삽입하는 알고리즘이다.
- tmp 과 arr[j] 를 비교하여, arr[j]의 값이 더 크면 arr[j] 의 값을 한칸씩 뒤로 보내면서 정렬한다.
- arr[j] 가 tmp 보다 작으면 한칸뒤에 tmp값을 넣고 j 루프를 종료한다.
시간복잡도
O(N^2)
(N-1)(회전1) + (N-2)(회전2) + .. + 2 + 1 -> N(N-1)/2 이므로 O(N^2)의 시간복잡도를 가진다.
합병 정렬
- 배열을 계속 균등한 크기로 분할하고, 분할된 부분을 정렬한 후 합해 전체가 정렬된 배열이 되게하는 정렬 방식
public static void merge_sort(int[] a, int left, int right) {
// 부분 리스트의 크기가 1이면 더 이상 쪼갤 수 없으므로 return 한다.
if (left == right) return;
int mid = (left + right) / 2;
merge_sort(a, left, mid); // 왼쪽 부분리스트(left ~ mid)
merge_sort(a, mid + 1, right); // 오른쪽 부분리스트(mid+1 ~ right)
merge(a, left, mid, right);
}
public static void merge(int[] a, int left, int mid, int right) {
int l = left; // 왼쪽 부분리스트 시작점
int r = mid + 1; // 오른쪽 부분리스트의 시작점
int idx = left; // 채워넣을 배열의 인덱스
while (l <= mid && r <= right) {
if (a[l] <= a[r]) {
sorted[idx] = a[l];
idx++;
l++;
} else {
sorted[idx] = a[r];
idx++;
r++;
}
}
if (l > mid) {
while (r <= right) {
sorted[idx] = a[r];
idx++;
r++;
}
} else {
while (l <= mid) {
sorted[idx] = a[l];
idx++;
l++;
}
}
for (int i = left; i <= right; i++) {
a[i] = sorted[i];
}
}
합병 정렬의 전체적인 과정
1. 주어진 리스트를 절반으로 분할하여 부분리스트로 나눈다. (분할)
2. 부분리스트의 크기가 1이 될때까지 반복한다.
3. 인접한 부분리스트끼리 합친다. (정복)
-
merge_sort() 메소드를 보면, mid라는 중간을 기점으로 두개의 배열로 나누는 것을 볼 수 있다.
-
merge_sort() 가 재귀를 돌면서, 왼쪽 부분 리스트가 1이 될 때까지 반복한다.
-
merge() 메소드를 보면, 2개의 부분리스트를 합치는데 idx를 통해 새로운 부분리스트(sorted[])에 값을 크기 비교하여 채워넣는다.
-
이때 각각의 부분리스트는 정렬이 되어있는 상태인데, 크기가 1인 부분리스트끼리 합치면서 크기가 2인 정렬된 부분리스트가 생긴다.
-
그렇게 다시 정렬된 크기가 2인 부분리스트끼리 합치면 정렬된 크기가 4인 부분리스트가 되기 때문에, merge()할때의 부분리스트들은 항상 정렬이 되어있는 상태이다.
-
-
마지막에 배열 a의 값을 배열 sorted를 통해 재할당해주는데, 이를 통해 리스트를 계속 부분정렬할 수 있다.
시간복잡도
pivot을 설정하는 과정없이 무조건 절반으로 리스트를 분할하며, 분할하는 과정(logN)을 N번 반복하기에 시간복잡도는 항상 NlogN이 나온다.
(항상 분할을 통해 탐색해야 할 부분리스트가 이전 부분리스트의 1/2로 줄어 logN의 시간복잡도가 나온다.)
단점으로는 임시배열인 sorted[]를 항상 만들어 사용하므로, 추가적인 메모리가 필요하다는 점이다.
퀵 정렬
- 합병 정렬과 같은 분할 정복 방식의 정렬로 pivot을 기준으로 왼쪽에는 pivot 보다 더 작은 값이 오게하고, 오른쪽에는 pivot을 기준으로 더 큰 값이 오게하며 부분 리스트를 쪼개 최종적으로는 전체리스트가 정렬이 되게하는 정렬 방식이다.
public class 퀵정렬 {
public static void sort(int[] a) {
l_pivot_sort(a, 0, a.length - 1);
}
//왼쪽 피벗 선택 방식
private static void l_pivot_sort(int[] a, int lo, int hi) {
if (lo >= hi) {
return;
}
int pivot = partition(a, lo, hi);
l_pivot_sort(a, lo, pivot - 1);
l_pivot_sort(a, pivot + 1, hi);
}
private static int partition(int[] a, int left, int right) {
int lo = left;
int hi = right;
int pivot = a[left];
while (lo < hi) {
while (a[hi] > pivot && lo < hi) {
hi--;
}
while (a[lo] <= pivot && lo < hi) {
lo++;
}
swap(a, lo, hi);
}
swap(a, left, lo);
return lo;
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}왼쪽 피벗 정렬 방식
-
항상 가장 왼쪽의 값을 피벗으로 설정한다.
-
hi가 pivot보다 작은 값이 나올 때까지 감소한다.
(조건 : lo < hi) -
lo가 pivot보다 큰 값이 나올 때까지 증가한다.
(조건 : lo < hi) -
2번과 3번 과정이 끝나면 서로 위치를 바꾼다.
4-1. 만약 2와 3의 과정에서 lo < hi를 만족하지 못하면, 제자리 교체가 이루어지고, pivot과 lo가 교환되는 방식으로 진행된다. -
이후 교환된 pivot(이전의 hi)을 기준으로 왼쪽과 오른쪽을 서로 다른 부분리스트로 잘라 같은 과정을 진행한다.
이런 방식으로 정렬이 가능한 이유는 pivot보다 작은 값은 왼쪽에 더 큰 값은 오른쪽에 치우치게 만들 수 있기 때문이다.
pivot을 설정하여, 왼쪽에는 더 작은 값들이 오게 만들고, 오른쪽에는 더 큰 값들이 오게 만들면서 해당 과정을 계속 반복하면 결국 크기가 1인 부분리스트들로 변하며, 최종적으로 전체리스트가 정렬된다.
위의 퀵정렬 소스코드를 보면 리스트를 분할리스트로 만든는 과정을 lo < hi까지 반복하는데, lo >= hi가 되면 부분리스트의 크기가 1이 되어 더이상 해당 과정을 반복할 이유가 없기 때문이다.
또한 재귀를 통해 부분리스트의 크기가 1이 될때까지 반복하여, 결국에는 pivot을 기준으로 양쪽 부분리스트들의 크기가 모두 1이되면서 왼쪽에는 pivot을 기준으로 더 작은 값이, 오른쪽에는 pivot을 기준으로 더 큰 값이 오게되어 최종적으로 전체리스트는 정렬이 된다.
시간복잡도
퀵정렬은 pivot에 따라 시간복잡도가 달라지는데, 이상적인 pivot을 선택했다면, 합병정렬과 동일하게 NlogN의 시간복잡도가 나온다.
(pivot이 해당 부분리스트의 중간값에 가까운 값일수록 이상적인 pivot에 가까워진다.)
그러나 최악의 pivot을 선택했다면, O(N^2)의 시간복잡도가 나온다.
