정렬 알고리즘
정렬이라는 것은 일종의 조건에 맞게 아이템들을 나열하는 것을 말한다. 이러한 정렬에도 여러가지 방식이 있으며 이를 하나하나 알아보자. 중간중간 이해가 잘 되지 않는다면 visualgo에서 관련된 sorting 을 재생해보면 도움이 될 것이다.
선택 정렬, Selection Sort
선택 정렬이란 앞쪽 index 부터 시작해서 마지막까지 값들을 확인하며 최솟값을 비교한다. 끝에 다다랐을 때 최솟값을 앞 index에 넣는다. 즉 앞 쪽부터 정렬되게 된다.
구현
이를 kotlin 으로 구현하면 아래와 같다.
var min_idx = 0
for (i in 0..arr.lastIndex-1) {
min_idx = i
for (j in i+1..arr.lastIndex) {
if (arr[min_idx] > arr[j]) min_idx = j
}
val term = arr[i]
arr[i] = arr[min_idx]
arr[min_idx] = term
}TimeComplexity
for문이 2개이므로 O(n^2)이 된다. 만약 이미 정렬되어 있는 array라 하더라도 끝까지 탐색해보아야 알 수 있기에 그대로 O(n^2)이다.
버블 정렬, Bubble Sort
버블 정렬이란 연속된 두 값을 비교해 더 큰 값이 뒤로 가도록 수행하는 정렬이다. 선택정렬과는 정 반대로 뒤에서 부터 큰 값들이 정렬된다.
구현
for (i in 0..arr.lastIndex-1) {
for (j in 0..arr.lastIndex-1-i) {
if (arr[j] > arr[j+1]) {
val term = arr[j]
arr[j] = arr[j+1]
arr[j+1] = term
}
}
}TimeComplexity
일반적으로는 for문이 2개이므로 O(n^2)이다. 위 구현에 정렬되어 있을 경우 바로 알고리즘을 끝내는 장치를 추가한다면, 이미 정렬된 array는 O(n)이 된다.
삽입 정렬, Insertion Sort
index를 기준으로 해당 index의 값을 그 앞 index의 값과 비교하여 더 작을 경우 swap하고, 더 클 경우 반복을 마치고 다음 index의 값을 새롭게 정렬하기 시작한다. 정렬을 시작할 index 이전의 값들은 모두 정렬되어 있다는 특징이 있다.
구현
for (i in 0..arr.lastIndex-1) {
for (j in i+1 downTo 1) {
if (arr[j] < arr[j-1]) {
val term = arr[j-1]
arr[j-1] = arr[j]
arr[j] = term
} else break
}
}TimeComplexity
이 또한 이중 for문 이므로 일반적으로는 O(n^2)이 된다. 허나 이미 정렬이 되어 있을 경우 바깥쪽 for 문은 n-1번 도는데 반해, 내부 for문은 바로 앞 값하고만 비교를 하고 끝나게 되어서 (1번 시행) O(n)이 된다.
병합 정렬, Merge Sort
배열을 같은 크기(or +1)로 나눠 분할한 배열을 각각 정렬한 후 합하는 알고리즘이며, 분할 정복(재귀를 통한)을 이용한다.
구현
세 가지 함수로 나눠서 구현해보았다.
1. split : 배열을 두 개로 자른다.
2. merge : 두 배열을 합치며 정렬한다. 각 배열의 pointer를 이용하여 더 작은 값이 앞에 오도록 배열하면 된다.
3. mergeSort : 재귀함수이며, mergeSort를 실행한다.
fun mergeSort(arr:List<Int>): List<Int> {
if (arr.size < 2) return arr
val (front, rear) = split(arr)
return merge(mergeSort(front), mergeSort(rear))
}
fun split(arr: List<Int>): Pair<List<Int>, List<Int>> {
val mid = arr.size / 2
return Pair(arr.subList(0, mid), arr.subList(mid, arr.size))
}
fun merge(left:List<Int>, right:List<Int>): List<Int> {
var l_idx = 0
var r_idx = 0
val result = mutableListOf<Int>()
while (l_idx < left.size && r_idx < right.size) {
val l_v = left[l_idx]
val r_v = right[r_idx]
if (l_v < r_v) {
result.add(l_v)
l_idx += 1
} else if (l_v > r_v) {
result.add(r_v)
r_idx += 1
} else {
result.add(l_v)
result.add(r_v)
l_idx += 1
r_idx += 1
}
}
if (l_idx < left.size) {
result.addAll(left.subList(l_idx, left.size))
}
if (r_idx < right.size) {
result.addAll(right.subList(r_idx, right.size))
}
return result
}
TimeComplexity
단계를 계속해서 2로 나눠가면 쪼개기 때문에 단계는 logN개가 생길 것이다. 또 각 단계를 합칠때 결국 비교되는 숫자는 N개이기 때문에 상수xN번 시행되므로 결국 N이 된다. 따라서 단계 x 각 단계별 계산이 시간복잡도가 될 것이므로 O(NlogN)이 된다. 위 3개의 정렬과 다르게 항상 평균적으로 좋은 시간 복잡도를 보여준다.
퀵 정렬, Quick Sort
퀵 정렬이란 배열에서 임의의 하나의 값을 정하고 해당 값을 pivot으로 하여 이보다 작은 값은 pivot보다 왼쪽에, 큰 값은 pivot보다 오른쪽에 배치시키는 방식으로 정렬한다. 이 또한 재귀적으로 진행되는데 한번 시행한 경우 pivot의 위치가 고정되므로, 이를 제외하고 왼쪽과 오른쪽의 배열에 대해서 QuickSort를 다시 시행하면 된다.
구현
index를 이용해 새로운 배열 생성없이 처리가 가능하다.
fun quickSort(arr: IntArray, start: Int, end: Int) {
if (start + 1 > end) return
val pivot = arr[end]
var i = start - 1
for (j in start..end-1) {
if (arr[j] < pivot) {
i += 1
val term = arr[j]
arr[j] = arr[i]
arr[i] = term
}
}
arr[end] = arr[i+1]
arr[i+1] = pivot
quickSort(arr, start, i) // pivot 기존 왼쪽 배열 정렬
quickSort(arr, i+2, end) // pivot 기존 오른쪽 배열 정렬
}
TimeComplexity
이러한 퀵 정렬은 배열이 pivot 기준으로 얼만큼 잘 짤리는지에 따라 결과가 많이 달라진다. 우선 최악의 경우는 pivot 기준으로 나머지 값이 모두 크거나, 모두 작은 경우이다. 이 경우 O(n^2)이 된다. 반면에 가장 이상적인 케이스의 경우 merge sort 처럼 매번 균등하게 분할이 될 경우이다. 이 경우 O(nlogn)이 된다. 평균적인 경우에는 O(nlogn)이 된다.
Merge Sort vs Quick Sort
merge sort는 평균적으로 O(nlogn)이 걸리고 quick sort 또한 평균적으로는 O(nlogn)이 걸린다. 여기에 quick sort의 경우에는 worst case에서는 O(n^2)으로 O(nlogn)인 merge sort에 비해 더 느린 케이스가 충분히 존재한다. 그럼에도 여러 자료들을 찾아보면 quick sort가 평균적으로 더 성능이 좋기에 이를 많이 활용한다고 한다. 이유가 뭘까 궁금해서 여러 내용을 찾아보았다.
- 정렬해야 하는 배열의 크기가 큰 경우에는 merge sort가, 작은 경우에는 quick sort가 성능이 더 좋다고 한다.
- merge sort는 추가 메모리 공간을 필요로 하는 반면, quick sort는 그렇지 않다.
- 참조의 지역성으로 인해 캐쉬의 도움을 많이 받는 quick sort가 일반적으로 더 빠르다.
여기서 지역성(Locality)이란 특정 부분의 정보를 집중적으로 참조하는 특성(?)이라고 할 수 있다. merge sort의 경우 넓은 범주의 값들을 계속해서 왔다갔다하며 참조하는 반면, quick sort의 경우 한정적인 범위에서 데이터들이 움직이며 시행이 거듭될수록 그 폭이 작아지므로 cache hit가 더 자주 일어나 "하드웨어"적으로 merge sort에 비해 더 우수하다.
