정렬(Sort) 알고리즘
정렬 알고리즘이란?
말그대로 정렬을 위한 것으로, 정렬은 일종의 조건에 맞게 요소들을 나열하는 것을 의미한다. 이 정렬 알고리즘은 종류가 다양한데 대표적인 것들을 하나씩 짧게 알아보도록 하자.
1. 선택 정렬(Selection Sort)
선택정렬 알고리즘은 앞 인덱스부터 시작하여 마지막 인덱스까지 값을 확인하며 최솟값을 비교하는 방식이다. 마지막에 도착했을때 최솟값을 앞 인덱스에 넣어 앞 쪽부터 정렬되도록 만든다.
시간복잡도는 O(n ^ 2)이다.
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
}
2. 버블 정렬(Bubble Sort)
버블정렬 알고리즘은 연속된 두 값을 비교하여 더 큰 값이 뒤로 가도록 수행하는 정렬 방식이다. 선택정렬과 달리 정 반대로 뒤에서부터 큰 값들이 정렬된다.
시간복잡도는 O(n ^ 2)이다.
단, 정렬이 이미 되어 있는 배열 기준으로 알고리즘에 종료하는 장치를 추가한다면 O(n)이다.
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
}
}
}
3. 삽입 정렬(Insertion Sort)
삽입정렬 알고리즘은 인덱스를 기준으로 해당 인덱스의 값을 그 이전 인덱스의 값과 비교하여 더 작을 경우 swap하고, 더 클 경우 반복을 종료하고 다음 인덱스의 값으로 넘어가 새롭게 정렬하는 방식이다. 정렬을 시작할 인덱스 이전의 값들은 모두 정렬되어 있다는 특징이 존재한다.
시간복잡도는 O(n ^ 2)이다.
단, 정렬이 이미 되어 있는 배열 기준으로 중첩반복문의 시행이 짧아지게 되어 O(n)이다.
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
}
}
}
4. 병합 정렬(Merge Sort)
병합정렬 알고리즘은 배열을 같은 크기로 나눠 분할한 배열을 각각 정렬한 뒤, 합하는 방식으로 분할 정복(재귀)을 이용한다.
시간복잡도는 O(N log N)이다.
단계를 계속 2로 나눠가며 쪼개기에 단계는 logN개가 생기고, 이 단계들을 합칠 때 결국 비교되는 수는 N개이므로 상수 * N번 시행은 즉 N이다. 그러므로 단계 * 각 단계별 계산이 시간복잡도가 되기 때문에 O(N log N)이다.
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
}
5. 퀵 정렬(Quick Sort)
퀵정렬 알고리즘은 배열에서 임의로 하나의 값을 정하고 해당 값을 기준으로 이보다 작은 값은 왼쪽, 큰 값은 오른쪽에 배치시키는 방식이다. 이 정렬 알고리즘 또한 재귀적으로 진행되며, 한번 시행한 경우 기준값의 위치가 고정되므로 이를 제외하고 왼쪽, 오른쪽 나눠진 배열에 대해 퀵정렬을 다시 시행하면 된다.
시간복잡도는 평균적으로 O(N log N)이다.
이러한 퀵정렬은 배열이 기준값으로 얼만큼 잘 나뉘느냐에 따라에 달린다.
최악을 상정했을때 기준값 제외 나머지 값이 모두 크거나 모두 작은 경우 즉, 임의로 잡은 값이 가장 크거나 가장 작은 경우이다. 이 경우 시간복잡도는 O(n ^ 2)이다.
반면 가장 이상적일 경우 병합정렬 알고리즘처럼 매번 균등하게 분할된다면, 이 경우 시간복잡도는 O(N log N)이다.
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 기존 오른쪽 배열 정렬
}
정렬 알고리즘 중 속도가 가장 빠른 것은?
평균적으로 시간복잡도도, 성능도 좋은 퀵정렬 알고리즘을 많이들 선호한다.
병합정렬 알고리즘 또한 평균적으로 시간복잡도가 퀵정렬 알고리즘과 마찬가지로 O(N log N)이 걸리지만, 평균적으로는 성능면에서 퀵정렬 알고리즘이 더 낫다고 한다.
병합정렬 알고리즘은 추가 메모리 공간이 필요하며 넓은 범주의 값을 계속 번갈아가며 참조하는 반면 퀵정렬 알고리즘의 경우 한정적인 범위에서 참조하며 시행할수록 그 범위가 더 작아지기 때문에 성능면에서 더 우수하다는 것.