Topic = 기본 정렬 알고리즘 학습해보기
Why
배열 정렬은 표준 라이브러리에서도 제공해주기 때문에 복잡한 경우가 아니라면 직접 다루는 경우가 적지만, 기본 제공 정렬 함수로 만족하지 못하는 상황에서 상황에 맞는 최적의 선택을 하기 위해선 학습이 필요할 것 같다.
버블 정렬
버블정렬은 배열의 모든 요소가 정렬될 때 까지 한 쪽 방향으로 인접한 두 요소를 비교하여 위치를 바뀌주는 작업을 반복하는 알고리즘이다.
➡️ 버블 정렬은 구현이 간단하고 쉽지만, O(N^2) 의 비효율적인 시간 복잡도를 갖고 있어 큰 데이터셋에서는 사용되지 않는다.
시간 복잡도 : O(N^2)
공간 복잡도 : O(1)
- 추가적인 메모리 사용이 거의 없는 제자리 정렬 알고리즘이다.
버블 정렬 작동 예시
fun bubbleSort(array: IntArray) {
val n = array.size
for (i in 0 until n - 1) {
for (j in 0 until n - i - 1) {
if (array[j] > array[j + 1]) {
val temp = array[j]
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
}
fun main() {
val array = intArrayOf(33, 34, 25, 12, 29, 1, 50)
bubbleSort(array)
}
선택 정렬
선택 정렬은 배열의 첫번째에 위치한 요소를 최소값으로 가정하여 시작해서, 배열을 순회하여 최소값을 찾고, 해당 최소값을 정렬에 맞게 위치시키는 방식이다.
- 배열을 순회하여 실제 최소값을 찾고, 해당 요소와의 위치를 바꾼다.
- 배열의 다음 위치로 이동하여 모든 요소가 정렬될 때 까지 1의 동작을 반복한다.
➡️ 선택 정렬도 구현이 간단하고 추가 메모리 사용이 거의 없지만, 비효율적인 시간 복잡도로 인해 큰 데이터 셋에서는 사용하기 어렵다.
시간 복잡도 : 매번 배열을 순회하기 때문에, 최악, 평균, 최선 모두 O(N^2) or θ(N^2) 의 시간 복잡도를 갖는다.
공간 복잡도 : O(1)
- 추가적인 메모리 사용이 거의 없는 제자리 정렬 알고리즘이다.
선택 정렬 작동 예시
// 선택 정렬 함수: 주어진 배열을 오름차순으로 정렬하는 함수
fun selectionSort(arr: IntArray) {
val n = arr.size
// 배열의 모든 요소를 순회
for (i in 0 until n - 1) {
// 최소값을 찾기 위한 시작점으로 i번째 요소를 초기값으로 설정
var minIdx = i
// i+1번째 요소부터 배열의 끝까지 최소값을 탐색
for (j in i + 1 until n) {
// 현재 최소값보다 더 작은 값을 찾으면 해당 인덱스를 최소값 인덱스로 업데이트
if (arr[j] < arr[minIdx]) {
minIdx = j
}
}
// 최소값을 찾았다면, i번째 요소와 최소값을 찾은 인덱스의 요소를 교환
val temp = arr[i]
arr[i] = arr[minIdx]
arr[minIdx] = temp
}
}
// 메인 함수: 선택 정렬을 실행하고 결과를 출력하는 함수
fun main() {
// 정렬할 배열 예시
val arr = intArrayOf(64, 25, 12, 22, 11)
// 선택 정렬 실행
selectionSort(arr)
// 정렬된 배열 출력
println("Sorted array: ${arr.joinToString()}")
}
삽입 정렬
삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 요소를 하나씩 정렬된 부분에 삽입하여 정렬하는 방식이다.
- 배열의 첫 번째 요소는 이미 정렬된 부분으로 간주하고 배열의 두번째 요소부터 시작된다.
- 정렬되지 않은 부분의 요소를 정렬된 부분의 적절한 위치로 이동시킨다.
- 요소를 적절한 위치로 삽입했다면, 다음 요소로 이동하여 모든 요소가 정렬이될 때까지 반복한다.
시간 복잡도 : O(N^2)
- 정렬되지 않은 부분의 요소를 정렬된 부분으로 삽입할 때, 삽입할 요소보다 작은 요소를 만날 때 까지 비교를 하며 이동하기 때문에 최악의 상황은 배열이 역순으로 정렬되어 있는 O(N^2)의 시간복잡도를, 배열이 이미 정렬되어 있는 최선의 경우에는 O(N)의 시간 복잡도를 갖는다.
공간 복잡도 : O(1)
➡️ 삽입 정렬은 데이터가 대부분 정렬된 상태에서 효율적이며, 실시간 데이터가 계속 입력되는 상황에서 유용하다.
삽입 정렬 작동 예시
// 삽입 정렬 함수: 주어진 배열을 정렬하는 함수
fun insertionSort(arr: IntArray) {
// 배열의 두 번째 요소부터 시작하여 배열의 마지막 요소까지 반복
for (i in 1 until arr.size) {
// 현재 요소를 key 변수에 저장
val key = arr[i]
// 이전 요소의 인덱스를 j에 저장
var j = i - 1
// 현재 요소(key)가 이전 요소보다 작고, 인덱스가 0보다 크거나 같을 때까지 반복
while (j >= 0 && arr[j] > key) {
// 현재 요소보다 큰 이전 요소를 한 칸 뒤로 이동
arr[j + 1] = arr[j]
j--
}
// 이동을 마친 후, 현재 요소를 적절한 위치에 삽입
arr[j + 1] = key
}
}
// 메인 함수: 삽입 정렬을 실행하고 결과를 출력하는 함수
fun main() {
// 정렬할 배열 예시
val arr = intArrayOf(64, 34, 25, 12, 22, 11, 90)
// 삽입 정렬 실행
insertionSort(arr)
// 정렬된 배열 출력
println("Sorted array: ${arr.joinToString()}")
}
힙 정렬
힙 정렬은 선택 정렬의 방식 중 하나로, 이진 힙 ( binary heap ) 자료구조를 사용하여 배열을 정렬하는 알고리즘이다.
- 배열을 이진 힙으로 구성한다. 최대 힙 ( max heap ) 을 사용하는 경우, 부모 노드는 자식 노드보다 항상 크거나 같으며, 이러한 성질을 만족하는 힙을 구성한다. 최소힙 ( min heap ) 을 사용하는 경우에는 반대로 부모 노드가 자식 노드보다 항상 작거나 같다.
- 힙의 최상위 노드부터 배열을 정렬 순서에 맞게 위치시킨다.
- 정렬이 되지 않은 나머지 노드로 다시 힙을 구성하여 모든 요소가 정렬될 때 까지 위 단계를 반복한다.
이진 힙 노드 예시 이미지
시간복잡도 : O(N log N)
- 평균적인 경우나 최선의 경우에도 다른 O(N log N) 정렬 알고리즘들 보다 느린 알고리즘으로 알려져있다.
공간 복잡도 : O(1)
힙 정렬 작동 예시
fun heapSort(arr: IntArray) {
val n = arr.size
// 배열을 최대 힙으로 구성
for (i in n / 2 - 1 downTo 0) {
heapify(arr, n, i)
}
// 하나씩 요소를 추출하여 정렬 수행
for (i in n - 1 downTo 1) {
// 현재 root와 마지막 요소를 교환
val temp = arr[0]
arr[0] = arr[i]
arr[i] = temp
// 축소된 힙에 대해 다시 heapify 수행
heapify(arr, i, 0)
}
}
// 최대 힙을 만드는 함수
fun heapify(arr: IntArray, n: Int, i: Int) {
var largest = i // 가장 큰 요소를 root로 초기화
val l = 2 * i + 1 // 왼쪽 자식
val r = 2 * i + 2 // 오른쪽 자식
// 왼쪽 자식이 부모보다 크면
if (l < n && arr[l] > arr[largest]) {
largest = l
}
// 오른쪽 자식이 현재 가장 큰 요소보다 크면
if (r < n && arr[r] > arr[largest]) {
largest = r
}
// 가장 큰 요소가 root가 아니면
if (largest != i) {
val swap = arr[i]
arr[i] = arr[largest]
arr[largest] = swap
// 재귀적으로 하위 트리에 대해 heapify 수행
heapify(arr, n, largest)
}
}
fun main() {
val arr = intArrayOf(12, 11, 13, 5, 6, 7)
heapSort(arr)
println("정렬된 배열 : ${arr.joinToString()}")
}
병합 정렬
병합 정렬은 큰 문제를 작게 나누어 해결하는 분할정복 알고리즘 정렬 방식으로 분할 단계에서 추가적인 배열의 공간이 필요한 정렬이다.
시간 복잡도 : 병합 정렬은 배열을 반으로 나누는 과정에서 log N, 각 단계마다 배열을 합치는 과정이 N 의 시간 복잡도를 가지므로 병합 정렬의 시간복잡도는 항상 O(N log N) 이다.
공간 복잡도 : O(N)
🟥 분할 - 정렬할 배열을 절반으로 나눈다
- ex) [ 25, 7, 14, 8, 15, 2, 20 ] 분할 ➡️ [ 25, 17, 14 ], [ 8, 15, 20, 2 ]
- 단계를 배열의 크기가 1이 될 때 까지 재귀적으로 반복한다 ex) [ 25, 17, 14 ], [ 8, 15, 20, 2 ] 분할 ➡️ [ 25 ], [ 17, 14 ], [ 8, 15 ], [ 20, 2 ]
🟪 정복 - 각 부분 배열을 재귀적으로 정렬한다.
- [ 25 ], [ 17, 14 ], [ 8, 15 ], [ 20, 2 ] ➡️ [ 25 ], [ 14, 17 ], [ 8, 15 ], [ 2, 20 ]
🟨 결합 - 두 개의 정렬된 부분 배열을 합쳐서 하나의 정렬된 배열을 만든다.
➡️ 아래 작동 예시에서 위 단계별 배경 색상으로 단계 구분하기.
병합 정렬 작동 예시
// 병합 정렬 함수: 주어진 배열을 정렬된 배열로 반환
fun mergeSort(arr: IntArray): IntArray {
// 배열의 크기가 1 이하인 경우 이미 정렬된 상태이므로 그대로 반환
if (arr.size <= 1) {
return arr
}
// 배열을 절반으로 나누기 위한 중간 인덱스 계산
val middle = arr.size / 2
// 배열을 왼쪽 절반과 오른쪽 절반으로 나눔
val left = arr.sliceArray(0 until middle)
val right = arr.sliceArray(middle until arr.size)
// 왼쪽과 오른쪽 절반을 각각 재귀적으로 병합 정렬하고, 정렬된 두 배열을 병합하여 반환
return merge(mergeSort(left), mergeSort(right))
}
// 병합 함수: 두 개의 정렬된 배열을 병합하여 하나의 정렬된 배열로 반환
fun merge(left: IntArray, right: IntArray): IntArray {
var leftIndex = 0
var rightIndex = 0
val merged = mutableListOf<Int>()
// 두 배열의 요소를 비교하면서 병합
while (leftIndex < left.size && rightIndex < right.size) {
if (left[leftIndex] <= right[rightIndex]) {
// 왼쪽 배열의 요소가 더 작거나 같은 경우 병합된 배열에 추가
merged.add(left[leftIndex])
leftIndex++
} else {
// 오른쪽 배열의 요소가 더 작은 경우 병합된 배열에 추가
merged.add(right[rightIndex])
rightIndex++
}
}
// 왼쪽 배열에 남은 요소들을 병합된 배열에 추가
while (leftIndex < left.size) {
merged.add(left[leftIndex])
leftIndex++
}
// 오른쪽 배열에 남은 요소들을 병합된 배열에 추가
while (rightIndex < right.size) {
merged.add(right[rightIndex])
rightIndex++
}
// 병합된 배열을 IntArray로 변환하여 반환
return merged.toIntArray()
}
// 메인 함수: 병합 정렬 함수 호출 및 결과 출력
fun main() {
val arr = intArrayOf(38, 27, 43, 3, 9, 82, 10)
val sortedArr = mergeSort(arr)
println("Sorted array: ${sortedArr.joinToString()}")
}
퀵 정렬
퀵 정렬도 분할정복법에 해당하는 정렬 알고리즘이다. 피봇( 기준점 ) 을 선택하여 피봇을 기준으로 피봇보다 큰 수, 작은 수로 분할하여 분할하여 정렬하는 것이다.
🟥 분할 - 정렬할 배열을 피봇을 기준으로 큰 수 / 작은 수로 나눈다.
- 이때 피봇을 배열의 중앙값으로 선택하느냐, 랜덤값으로 선택하느냐, 배열의 첫,마지막 번째 값으로 선택하느냐에 따라 시간 복잡도의 차이가 존재한다. 보통 중앙값이 최악의 경우를 피하는 데 효과적이다.
- [ 4, 2, 5, 7, 3, 1, 6 ] 의 배열에서 랜덤으로 뽑은 피봇이 3일 경우 ➡️ [ 2, 1 ], [ 3 ], [ 4, 5, 7, 6 ]
🟪 정복 - 피벗을 기준으로 분할된 두개의 부분 배열을 재귀적으로 정렬한다.
- [ 1, 2 ], [ 3 ], [ 4, 5, 6, 7 ]
🟨 결합 - 퀵 정렬은 분할, 정복 단계에서 모든 정렬 작업이 수행되기 때문에, 기본적으로 결합 단계가 필요 없는 알고리즘
➡️ 아래 작동 예시에서 위 단계별 배경 색상으로 단계 구분하기.
시간 복잡도 : 평균 O(N log N) , 최악의 경우 O(N^2)
퀵 정렬 작동 예시
// 퀵 정렬 함수
fun quickSort(arr: IntArray, low: Int, high: Int) {
if (low < high) {
// 파티션 함수를 사용하여 피벗을 기준으로 배열을 두 부분으로 나눔
val pi = partition(arr, low, high)
// 재귀적으로 피벗의 왼쪽 부분을 정렬
quickSort(arr, low, pi - 1)
// 재귀적으로 피벗의 오른쪽 부분을 정렬
quickSort(arr, pi + 1, high)
}
}
// 파티션 함수: 피벗을 기준으로 배열을 두 부분으로 나누는 함수
fun partition(arr: IntArray, low: Int, high: Int): Int {
val pivot = arr[high] // 피벗을 배열의 마지막 요소로 선택
var i = (low - 1) // 작은 요소의 인덱스
for (j in low until high) {
// 현재 요소가 피벗보다 작거나 같은 경우
if (arr[j] <= pivot) {
i++
// arr[i]와 arr[j]를 교환
val temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
// arr[i+1]과 피벗을 교환하여 피벗을 올바른 위치에 배치
val temp = arr[i + 1]
arr[i + 1] = arr[high]
arr[high] = temp
return i + 1 // 피벗의 새 인덱스를 반환
}
// 메인 함수: 퀵 정렬을 실행하고 결과를 출력하는 함수
fun main() {
val arr = intArrayOf(10, 7, 8, 9, 1, 5) // 정렬할 배열
val n = arr.size
quickSort(arr, 0, n-1) // 퀵 정렬 실행
println("Sorted array: ${arr.joinToString()}") // 정렬된 배열 출력
}
[ A. 오늘 복습한 내용 / B. 다음에 학습할 내용 ]
A. X
B. Timsort 등 다양한 정렬 알고리즘 학습해보기
[오류,에러 등등]
1. 병합 정렬 피그마 애니메이션에 병합 시 1 외에 다른 숫자들이 보였다가 사라지는 문제.
해결방법 ➡️ 1이 구분선 위에 쌓이기 전 92 프레임에 91 프레임과 같이 모든 요소의 opacity 값을 0으로 지정해뒀었는데, 1개만 남겨두고 지우니까 해결되었다.
[느낀 점]
1. 간단한 애니메이션을 만들어봤는데 재미있는 것 같다. 모션이 자동으로 적용되는거라 어떤 요소는 슬라이드 되면서 나오고 어떤 요소는 제자리에서 나오고 제각각인 게 아쉽다. 기회가 되면 애니메이션도 학습해봐야겠다.
[Reference]
정렬 알고리즘
정렬 알고리즘을 소리로 표현한 영상이다. 최신판인 0.6.5버전 을 다운로드 받으면 위키 정렬등이 포함된 총 30
namu.wiki
'CS' 카테고리의 다른 글
| [CS] 프로그램 ( Program ), 프로세스 ( Process ), 쓰레드 ( Thread ) 학습 - 작성중 (1) | 2024.04.30 |
|---|---|
| [TIL] Kotlin - 재귀 함수, 꼬리재귀 ( Tailrec ) 함수 (1) | 2024.04.20 |
| [TIL] 계산 복잡도 - 시간복잡도 ( Time Complexity ) 1. 개념, 점근적 표기법 (0) | 2024.04.14 |
