[Kotlin] 정렬 1 (버블정렬, 선택정렬, 삽입정렬)

Algorithm

[Kotlin] 정렬 1 (버블정렬, 선택정렬, 삽입정렬)

빠쿤 2021. 12. 15. 21:25

1. 버블정렬 (Bubble Sort)

인접한 두 값을 비교하여 뒤의 값이 더 작을 시 swap을 수행하는 정렬이다.

배열을 한 번 순회 할 때마다 배열의 맨 뒤 index부터 가장 큰 값이 정렬된다.

버블정렬 Kotlin Code

// 바깥쪽 loop(배열을 순회할 횟수)
for (i in 0 until n - 1) {
    var isSwap = false
    // 안쪽 loop(swap 여부를 판단할 횟수)
    // 바깥쪽 loop가 한 번 돌 때마다 배열의 끝에 정렬된 값이 들어오므로 n - 1 - i
    for (j in 0 until n - 1 - i) {
        if (array[j] > array[j + 1]) {
            swap(array, j, j + 1)
            isSwap = true
        }
    }

    // 정렬이 완료된 경우 바로 return (시간복잡도 감소)
    if (!isSwap) {
        return
    }
}

(i) 바깥쪽 loop는 배열을 순회하는 횟수이다. 배열을 1번 순회 할 때마다 맨 뒤의 Index에 정렬된 값이 배치되며, index = 0의 경우는 이미 1 ~ n-1까지 정렬이 모두 완료된 상태이므로 정렬할 필요가 없다. 그러므로 loop는 0 until n-1이다.

(j) 안쪽 loop는 비교할 두 값의 index를 나타낸다. 바깥쪽 loop가 수행 될 때마다 배열의 맨 뒤에 정렬된 값이 배치 되므로, i의 값은 이미 정렬된 값의 개수와 동일하다. 이미 정렬된 값에 대한 비교는 필요하지 않으므로 loop는 0 until n - 1 - i 이다.

이 때, 안쪽 loop가 모두 돌 때 까지 1번도 swap이 일어나지 않았다면 모든 index에 대해 정렬이 완료된 경우이므로 정렬을 종료한다.

시간 복잡도 :

n과 연관된 loop가 2개이므로 최악의 경우 Big-O 표기법에 따라 O(n^2)이다. (실제로는 n(n-1) / 2)

완전 정렬된 경우, 안쪽의 loop만 돌고 정렬을 종료하므로 O(n)이다.

2. 선택정렬 (Selection Sort)

앞 index를 기준점으로 하여 배열을 순회하며 최솟값을 비교한다.

배열의 끝에 도달했을 때, 저장된 최솟값을 앞 index에 넣는다.

배열을 한 번 순회 할 때마다 앞의 index에 정렬된 값이 채워진다.

선택정렬 Kotlin Code

var min: Int
// 마지막 값은 정렬할 필요 없으므로 0 until n - 1
for (i in 0 until n - 1) {
    // 초기 index를 최솟값 index로 설정
    min = i
    // 초기 index의 다음 index부터 마지막 index까지 순회
    for (j in i+1 until n) {
        // 값 비교 후 mininum index 변경
        if (array[min] > array[j]) min = j
    }
    // 최솟값을 앞에 배치
    swap(array, i, min)
}

(i) 바깥쪽 loop는 정렬된 Index를 제외한 최솟값이 들어갈 가장 앞에 있는 index이다. min 값을 i로 초기화 하여 내부 loop를 통해 값의 비교를 시작한다. 맨 앞부터 차례로 정렬된 값이 채워지므로, 마지막 index는 정렬할 필요가 없기 때문에 loop는 0 until n-1이다.

(j) 안쪽 loop는 현재 최솟값과 비교할 값의 index이다. 현재 최솟값(arr[min]) 보다 현재 값(arr[j])이 더 클 경우 min = j 로 바꾸어 현재 index를 최솟값 index로 변경한다. 최솟값이 들어갈 index의 값은 초기에 min = i를 통해 저장하였으므로, loop는 i+1 until n이다.

시간 복잡도 :

n과 연관된 loop가 2개이므로 최악의 경우 Big-O 표기법에 따라 O(n^2)이다. (실제로는 n(n-1) / 2)

완전 정렬된 경우에도 loop 2개를 모두 돌 때까지 완전 정렬됨을 알 수 없으므로 똑같이 O(n^2)이다.

3. 삽입정렬 (Insertion Sort)

앞 index를 기준점으로 하여 기준값과 그 앞에 있는 값들을 차례로 비교하여 기준값을 알맞은 앞 index에 삽입하는 정렬이다.

기준값과 그 앞 index의 값을 차례로 비교하여 기준값이 더 작을 경우 swap, 더 클 경우 정렬을 마치고 다음 index의 정렬을 시작한다.

삽입정렬 Kotlin Code

// 첫번째 값은 삽입의 대상이 아니므로 0 until n-1
for (i in 0 until n - 1) {
    // i + 1 번째 값에 대해 삽입 대상으로 지정
    for (j in i + 1 downTo 1) {
        // j - 1 값과 비교하며 더 작을 시 앞 index로 이동
        if (array[j] < array[j - 1]) swap(array, j, j - 1)
        // j - 1이 더 작을 시 비교 종료
        else break
    }
}

(i) 바깥쪽 loop는 정렬을 수행하는 횟수이다. 해당 loop가 1번 수행 될 때마다 하나의 Index가 정렬되며, 마지막 index의 경우에는 이미 0 ~ n-1 번째 index가 모두 정렬된 상태이므로 정렬할 필요가 없다. 그러므로 loop는 0 until n-1이다.

(j) 안쪽 loop는 비교할 기준값의 index를 나타낸다. index 0은 앞에 비교할 대상이 없고, i index의 경우에는 이미 정렬이 수행된 index이므로 i + 1 부터 시작한다. j의 값을 1씩 down 시키며 j와 j-1의 값을 비교한다. j가 j-1의 값보다 작을 경우 swap한 후 loop를 마저 수행하며, j가 j-1보다 클 경우 정렬이 완료된 것이므로 loop를 break 한다. loop는 i+1 downTo 1이다.

* downTo(n) : n씩 값을 감소시키며 loop 수행. 매개변수 생략 시 1씩 감소.

시간 복잡도 :

n과 연관된 loop가 2개이므로 최악의 경우 Big-O 표기법에 따라 O(n^2)이다. (실제로는 n(n-1) / 2)

완전 정렬된 경우, 안쪽 loop가 1번만 수행되고 모두 break 되어 바깥 쪽 loop만 n-1번 수행되므로 O(n)

참고, gif 출처 :

https://commons.wikimedia.org/wiki/File:Bubble-sort.gif

File:Bubble-sort.gif - Wikimedia Commons

No higher resolution available.

commons.wikimedia.org

https://algorithms.tutorialhorizon.com/selection-sort-java-implementation/selection-sort-gif/

Selection Sort Gif | Algorithms

algorithms.tutorialhorizon.com