[Algorithm] 정렬 알고리즘 1 ~ 삽입, 선택, 병합, 힙 정렬 ~ (Kotlin)

정렬의 뜻은 이 글을 보는 사람이면 모두 알겠지만 사전적 의미는 아래와 같다.

 

가지런하게 줄지어 늘어섬 또는 그렇게 늘어서게 함, 데이터를 특정 조건에 따라 일정 순서가 되게 재배열하는 일

 

규칙 없이 막 늘어놓은 것들을 특정 규칙에 따라 정리한다는 걸로 이해할 수 있겠다. 아래는 정렬 알고리즘에 대한 영문 위키백과의 설명이다.

 

https://en.wikipedia.org/wiki/Sorting_algorithm

Sorting algorithm - Wikipedia

정렬 알고리즘은 리스트의 요소를 순서대로 정렬하는 알고리즘이다. 가장 자주 쓰이는 정렬 방식은 숫자 순서, 사전적 순서, 오름차순 또는 내림차순이다. 효율적인 정렬은 입력 데이터를 정렬된 리스트로 만들어야 하는 다른 알고리즘의 효율성을 최적화하는 데 중요하다. 정렬은 데이터를 표준화하고 사람이 읽을 수 있는 출력을 만드는 데도 유용하다
공식적으로 모든 정렬 알고리즘의 출력은 2가지 조건을 만족해야 한다

1. 출력은 단조로운 순서(각 요소가 필요한 순서에 따라 이전 요소보다 작거나 크지 않음)로 이뤄진다
2. 출력은 입력의 순열(순서를 바꾸지만 원래 요소는 모두 유지)이다

일부 알고리즘은 순차적 접근을 위해 설계됐지만 가장 성능이 좋은 알고리즘은 데이터가 무작위 접근을 허용하는 데이터 구조에 저장돼 있다고 가정한다
정렬 문제는 간단하고 친숙한 문제지만 효율적으로 풀기 어렵다는 복잡성 때문에 컴퓨팅이 시작된 이래로 많은 연구가 되어왔다. 점근적으로 최적의 알고리즘은 20세기 중반부터 알려져 왔으며 널리 쓰이는 Timesort는 2002년, 라이브러리 정렬은 2006년에 처음 발표되는 등 새 알고리즘이 계속 발명되고 있다...(중략)

 

이 문서의 스크롤을 밑으로 내리면 정렬 알고리즘들의 종류들이 표로 정리돼 있다. 좀 더 밑에는 인기 있는 정렬 알고리즘들의 종류들이 쓰여 있다. 위에서 몇 가지만 적어 보면 아래와 같다. 알고리즘의 개수가 많아서 몇 개만 적었다.

 

• 삽입 정렬
• 선택 정렬
• 병합 정렬
• 힙 정렬
• 퀵 정렬
• 쉘 정렬
• 버블 정렬
• 빗질 정렬
• 교환 정렬
• 카운팅 정렬
• 버킷 정렬
• 기수 정렬

 

현재 온라인 서점에서 판매되는 알고리즘 책의 인덱스에서 정렬 파트를 확인하면 위 알고리즘 중 몇 개는 반드시 포함되어 있다. 아래부턴 삽입 정렬부터 힙 정렬까지 간단히 알아보고, 코틀린으로 어떻게 구현할 수 있는지 확인한다. 다른 정렬들은 다음 포스팅에서 확인한다.

 

삽입 정렬

 

https://en.wikipedia.org/wiki/Insertion_sort

Insertion sort - Wikipedia

삽입 정렬은 비교를 통해 한 번에 한 항목씩 최종 정렬된 배열(또는 리스트)을 만드는 간단한 정렬 알고리즘이다. 퀵 정렬, 힙 정렬 또는 병합 정렬 같은 고급 알고리즘에 비해 큰 리스트에선 효율성이 떨어진다. 아래는 삽입 정렬의 몇 가지 장점이다

- 구현이 간단하다 : 존 벤틀리는 C와 유사한 의사 코드로 3줄 버전, 최적화된 5줄 버전을 보였다
- 다른 이차(O(n^2)) 정렬 알고리즘과 마찬가지로 작은 데이터 세트에 효율적이다
- 선택 정렬, 버블 정렬 같은 대부분의 다른 단순한 2진법 알고리즘보다 효율적이다
- 적응형, 즉 이미 상당히 정렬된 데이터 세트에 효율적이다. 입력의 각 요소가 정렬된 위치에서 k 이상 떨어져 있지 않을 때 시간 복잡도는 O(k)다
- 안정적이다 : 같은 키를 가진 요소의 상대적 순서를 바꾸지 않는다
- In-place : 일정량의 추가 메모리 공간만 필요하다
- Online : 리스트를 받으면 리스트를 정렬할 수 있다

삽입 정렬은 반복할 때마다 입력 요소를 하나씩 소모해서 정렬된 출력 리스트를 늘린다. 삽입 정렬은 반복할 때마다 입력 데이터에서 하나의 요소를 제거하고 정렬된 리스트 안에서 해당 요소가 속한 위치를 찾아서 그 위치에 삽입한다. 입력 요소가 남지 않을 때까지 반복한다. 정렬은 일반적으로 배열을 반복해서 그 뒤에 정렬된 리스트를 늘리는 방식으로 제자리에서 수행된다. 각 배열 위치에서 정렬된 리스트에서 가장 큰 값(이전에 확인된 배열 위치에서 그 옆에 있는 값)과 비교해서 그 값을 확인한다. 더 크면 그 요소를 제자리에 두고 다음 요소로 이동한다. 더 작으면 정렬된 리스트 안에서 올바른 위치를 찾아 더 큰 값을 위로 이동시켜 공백을 만든 다음 올바른 위치에 삽입한다. k번의 반복 후 결과 배열은 처음 k+1(첫 아이템은 건너뛰기 때문에 1을 더함) 항목이 정렬되는 속성을 갖는다. 각 반복에서 입력의 첫 번째 남은 항목이 제거되고 올바른 위치의 결과에 삽입되어 결과가 확장된다

(중략)...가장 좋은 입력은 이미 정렬된 배열이다. 이 때 삽입 정렬은 선형 실행 시간(O(n))을 갖는다. 각 반복 동안 첫 번째 남은 요소는 배열의 정렬된 하위 섹션의 가장 오른쪽 요소와만 비교된다. 가장 최악의 입력은 역순 정렬된 배열이다. 모든 최악의 경우 입력의 집합은 각 요소가 앞의 요소 중 작거나 2번째로 작은 요소인 모든 배열로 구성된다. 이 경우 내부 루프의 모든 반복은 다음 요소를 삽입하기 전에 배열의 정렬된 하위 섹션 전체를 스캔하고 이동한다. 따라서 삽입 정렬은 O(n^2)의 실행 시간을 갖는다...(중략)

 

삽입 정렬은 구현은 간단하지만 이미 어느 정도 정렬돼 있는 입력을 받을 때 좋은 효율을 내는 알고리즘이다.

아래는 코틀린으로 삽입 정렬을 구현한 예시다.

 

fun main() {
    val arr = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    println("정렬 전: ${arr.contentToString()}")
    insertionSort(arr)
    println("정렬 후: ${arr.contentToString()}")
}

fun insertionSort(arr: IntArray) {
    for (i in 1 until arr.size) {
        val key = arr[i]
        var j = i - 1

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
}

// 정렬 전: [64, 34, 25, 12, 22, 11, 90]
// 정렬 후: [11, 12, 22, 25, 34, 64, 90]

 

insertionSort() 안의 반복문에서 1부터 시작하는 것은 2번째 요소부터 시작한다는 뜻이다. 왜냐면 삽입 정렬에서 1번째 요소는 이미 정렬된 것으로 간주하기 때문이다. 그리고 주어진 배열의 끝까지 순회하며 각 반복마다 현재 아이템을 key 변수에 담는다. key 변수는 현재 삽입하려는 값(arr[i])이다.

그 안에 있는 while문에선 i-1에서 시작해 배열 왼쪽으로 이동하면서 key값보다 큰 요소를 찾는다. arr[j]가 key보다 크면 그 요소는 오른쪽 뒤로 이동한다. 인덱스 상에선 1을 더하면 오른쪽으로 이동하는 것이 되니 arr[j + 1] = arr[j]가 된다. 이것은 key보다 작은 값이 나올 때까지 or 배열의 맨 앞까지 반복한다. 즉 while문은 새 값을 넣을 자리를 찾기 위해 새 값을 기존 값들과 비교하면서 뒤로 밀어내는 역할을 수행한다. key보다 큰 값이 존재하는 동안 계속 실행된다는 게 핵심이다.

이 과정들이 앞서 말한 대로 배열의 모든 요소에 적용되고 정렬 전, 후 배열을 출력하면 정렬 후에는 순서대로 정렬된 것을 볼 수 있다.

for문 안에서 while문을 사용하기 때문에 이 알고리즘은 최악의 경우 O(n^2)의 시간 복잡도를 갖지만, 거의 정렬된 배열을 받는다면 각 요소를 비교하는 과정이 단축되기 때문에 O(n)의 시간 복잡도를 가질 수 있다. 그러나 제자리 정렬 알고리즘이라 입력 배열 외에 추가 메모리를 거의 쓰지 않고 배열 안에서 값을 바꾸거나 이동시키면서 정렬하기 때문에 공간 복잡도는 O(1)이다.

 

삽입 정렬의 작동 원리는 아래와 같다.

 

• 배열을 정렬된 부분, 정렬되지 않은 부분으로 나눈다
• 정렬되지 않은 부분에서 요소를 하나씩 가져와서 정렬된 부분의 적절한 위치에 삽입한다
• 이 과정을 반복해서 전체 배열을 정렬한다

 

선택 정렬

 

https://en.wikipedia.org/wiki/Selection_sort

Selection sort - Wikipedia

선택 정렬은 제자리 비교 정렬 알고리즘이다. 이 알고리즘의 시간 복잡도는 O(n^2)라서 큰 리스트에선 비효율적이고 비슷한 삽입 정렬보다 성능이 떨어진다. 선택 정렬은 단순성으로 유명하며 보조 배터리가 제한된 특정 상황에서 더 복잡한 알고리즘보다 성능 면에서 유리하다. 이 알고리즘은 입력 리스트를 리스트 앞(왼쪽)에서 오른쪽으로 쌓이는 정렬된 하위 리스트, 리스트의 나머지 부분을 차지하는 정렬되지 않은 나머지 항목의 하위 리스트 두 부분으로 나뉜다. 처음엔 정렬된 하위 리스트가 비어 있고 정렬되지 않은 하위 리스트가 전체 입력 리스트다. 알고리즘은 정렬되지 않은 하위 리스트에서 가장 작은(또는 정렬 순서에 따라 가장 큰) 요소를 찾아 가장 왼쪽의 정렬되지 않은 요소와 스왑하고(정렬 순서대로 배치), 하위 리스트 경계를 오른쪽으로 한 요소 이동하는 식으로 진행된다. 선택 정렬의 시간 효율은 이차적이므로 선택 정렬보다 시간 복잡도가 더 높은 정렬 기법이 여럿 있다
이차 정렬 알고리즘(단순 평균값이 O(n^2)인 정렬 알고리즘)에서 선택 정렬은 항상 버블 정렬, 그놈 정렬보다 성능이 뛰어나다. 삽입 정렬은...(중략)...k+1번 요소를 찾기 위해 나머지 요소를 모두 스캔해야 한다. 삽입 정렬은 일반적으로 선택 정렬보다 절반의 비교를 수행하지만 정렬 전 배열의 순서에 따라 비슷하거나 훨씬 적은 비교를 수행할 수 있다. 그러나 배열이 이미 정렬됐거나 정렬에 가까운 경우 훨씬 효율적으로 수행된단 점에서 삽입 정렬의 장점이 더 많다...(중략)

 

시간 복잡도는 삽입 정렬에서 최악의 경우와 동일하다. 버블 정렬, 그놈 정렬이란 정렬 알고리즘보다 좀 더 효율적이며 상황에 따라선 선택 정렬보다 삽입 정렬을 쓰는 편이 더 나을 수 있다.

아래는 코틀린으로 선택 정렬을 구현한 예시다.

 

fun selectionSort(arr: Array<Int>) {
    val n = arr.size

    for (i in 0 until n - 1) {
        var minIndex = i

        for (j in i + 1 until n) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }

        val temp = arr[minIndex]
        arr[minIndex] = arr[i]
        arr[i] = temp
    }
}

fun main() {
    val arr = arrayOf(64, 25, 12, 22, 11)
    println("정렬 전 : ${arr.joinToString(", ")}")

    selectionSort(arr)

    println("정렬 후 : ${arr.joinToString(", ")}")
}

// 정렬 전 : 64, 25, 12, 22, 11
// 정렬 후 : 11, 12, 22, 25, 64

 

배열의 요소들을 순회하면서 해당 인덱스 이후 배열에서 최소값을 찾고 그 최소값을 현재 인덱스와 교환하는 방식으로 작동한다. i는 정렬될 위치를 말하고 minIndex는 그 위치부터 끝까지 중에서 가장 작은 최소값의 인덱스를 저장할 변수다.

2번째 for문에서 j는 i 인덱스 이후의 요소들을 순회하면서 arr[j]가 arr[minIndex]보다 작은지 확인한다. 이 때 더 작은 값이 발견되면 minIndex를 그 인덱스로 업데이트한다.

모든 루프가 끝나면 minIndex에 해당하는 값을 arr[i]와 교환한다. 이 처리 때문에 i번 요소는 배열에서 올바른 곳에 위치하게 된다.

작동 흐름을 적으면 아래와 같다.

 

• 1번째 반복
  • 배열의 0번~마지막 인덱스 중에서 가장 작은 값을 찾는다. 11이 가장 작기 때문에 64와 위치가 바뀐다
  • 11, 25, 12, 22, 64
• 2번째 반복
  • 1번째 인덱스~마지막 인덱스 중에서 가장 작은 값을 찾는다. 12가 가장 작기 때문에 25와 교환한다
  • 11, 12, 25, 22, 64
• 3번째 반복
  • 2번째 인덱스~마지막 인덱스 중에서 가장 작은 값을 찾는다. 22가 가장 작기 때문에 25와 교환한다
  • 11, 12, 22, 25, 64
• 4번째 반복
  • 값들이 이미 정렬된 상태 -> 추가 교환 없이 로직 종료

 

선택 정렬의 시간 복잡도는 언제나 O(n^2)다. 배열이 정렬되어 있든 말든 항상 최소값을 찾기 위해 배열 안의 모든 요소들을 순회하기 때문이다. 그러나 삽입 정렬과 동일하게 제자리 정렬 알고리즘이라 추가로 메모리를 사용하지 않기 때문에 공간 복잡도는 O(1)이다. 제자리 정렬 알고리즘의 이런 특징 때문에 메모리가 제한된 환경에선 성능에 유리한 정렬 알고리즘이라 볼 수 있다.

 

병합 정렬

 

https://en.wikipedia.org/wiki/Merge_sort

Merge sort - Wikipedia

병합 정렬은 효율적이고 범용적인 비교 기반 정렬 알고리즘이다. 대부분의 구현은 안정적 정렬을 만드는데 이건 입출력에서 같은 요소의 상대적 순서가 동일하단 걸 의미한다. 병합 정렬은 1945년 폰 노이만이 만든 분할 정복 알고리즘이다. 개념적으로 병합 정렬은 아래와 같이 작동한다

1. 정렬되지 않은 리스트를 각각 하나의 요소를 포함하는 n개의 하위 리스트로 나눈다. 하나의 요소로 구성된 리스트는 정렬됐다고 간주한다
2. 하위 리스트가 하나만 남을 때까지 하위 리스트를 반복 병합해서 정렬된 새 하위 리스트를 만든다. 이것이 정렬된 리스트가 된다

...(중략) n객체를 정렬할 때 병합 정렬의 평균 및 최악의 경우 성능은 O(n log n) comparison이다...(중략)...최악의 경우 병합 정렬은 평균적인 경우의 퀵 정렬보다 약 39% 적은 비교를 사용하며, 이동 측면에서 병합 정렬의 최악의 복잡성은 퀵 정렬의 최상의 경우와 동일한 O(n log n)이다. 정렬할 데이터가 순차적으로만 효율적으로 접근할 수 있는 경우 일부 유형의 리스트에서 병합 정렬이 퀵 정렬보다 효율적이므로 순차 접근하는 데이터 구조가 매우 일반적인 리스프 같은 언어에서 널리 쓰인다. 빠른 정렬의 일부 구현과 달리 병합 정렬은 안정적인 정렬이다
병합 정렬의 가장 일반적인 구현은 제자리 정렬이 아니므로 정렬된 출력을 저장할 입력의 메모리 크기를 할당해야 한다...(중략)

 

병합 정렬은 분할 정복 알고리즘이라고 한다. 분할 정복 알고리즘이 무엇인지 확인한다.

 

https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm

Divide-and-conquer algorithm - Wikipedia

분할 정복은 알고리즘 설계 패러다임이다. 이 알고리즘은 문제를 직접 해결할 수 있을 만큼 단순해질 때까지 재귀적으로 같거나 관련된 유형의 2개 이상의 하위 문제로 분해한다. 그 다음 하위 문제의 해를 결합해 원래 문제에 대한 해를 구한다. 분할 정복 기법은 정렬(퀵 정렬, 병합 정렬), 큰 수 곱하기(카라츠바 알고리즘), 가장 가까운 점 쌍 찾기, 구문 분석(하향식 파서), 이산 푸리에 변환(FFT) 등 많은 문제에 대한 효율적인 알고리즘의 기초다
수학적 귀납법에서와 마찬가지로 문제를 일반화해서 재귀적 해를 구할 수 있게 만들어야 하는 경우가 많다. 분할 정복 알고리즘의 정확성은 일반적으로 수학적 귀납에 의해 증명되며, 계산 비용은 종종 재귀 관계를 풀어서 결정된다
분할 정복 패러다임은 종종 문제의 최적인 해결책을 찾는 데 쓰인다. 기본 아이디어는 주어진 문제를 2개 이상의 유사하지만 더 간단한 하위 문제로 분해해서 차례로 해결하고, 그 해결책을 구성해서 문제를 해결하는 것이다. 주어진 n개의 자연수 리스트를 정렬하려면 이걸 n / 2개의 숫자로 구성된 2개의 리스트로 나누고, 각 리스트를 차례로 정렬한 다음 두 결과를 결합해서 주어진 리스트의 정렬 버전을 얻는다. 이런 접근 방식을 병합 정렬 알고리즘이라고 한다
분할 정복이란 이름은 정렬된 리스트에서 레코드를 찾기 위한 이진 검색 알고리즘(또는 수치 계산의 아날로그인 근 찾기용 이등분 알고리즘)과 같이 각 문제를 하나의 하위 요소로 축소하는 알고리즘에 적용되기도 한다. 이런 알고리즘은 일반적인 분할 정복 알고리즘보다 효율적으로 구현할 수 있으며, 특히 꼬리 재귀를 쓰는 경우 단순 루프로 변환할 수 있다. 그러나 이런 광범위한 정의에 따르면 재귀 또는 루프를 쓰는 모든 알고리즘은 분할 정복 알고리즘으로 간주될 수 있다. 따라서 일부는 각 문제가 둘 이상의 하위 문제를 만들 수 있을 때만 분할 정복이라 해야 한다고 생각한다...(중략)...각 단계에서 상수 계수만큼 검색 공간을 축소(가지치기)하면 전체 알고리즘은 축소 단계와 같은 점근 복잡도를 가지며 상수는 축소 계수에 따라 달라진다. 이를 가지치기 및 검색(prune and search)이라고 한다...(중략)

분할 정복은 개념적으로 어려운 문제를 해결하기 위한 도구로 문제를 하위 문제로 나눠서 사소한 경우를 해결하고 하위 문제를 원래 문제와 결합하는 방법만 있으면 된다. 감소 정복은 n의 탑을 n-1의 탑으로 옮기는 고전적인 하노이 탑 문제와 같이 문제를 하나의 작은 문제로 축소하기만 하면 된다...(중략)

 

병합 정렬이 작동하는 흐름을 요약하면 아래와 같다.

 

• 한 리스트를 같은 크기의 리스트 2개로 분할한다
• 분할된 부분 리스트들을 정렬한다
• 정렬된 부분 리스트들을 하나로 합치면 전체 정렬된 리스트가 되도록 한다

 

병합 정렬을 코틀린으로 구현한 예시는 아래와 같다.

 

fun mergeSort(arr: Array<Int>): Array<Int> {
    if (arr.size <= 1) return arr

    val mid = arr.size / 2
    val left = arr.sliceArray(0 until mid)
    val right = arr.sliceArray(mid until arr.size)

    return merge(mergeSort(left), mergeSort(right))
}

fun merge(left: Array<Int>, right: Array<Int>): Array<Int> {
    var leftIndex = 0
    var rightIndex = 0
    val result = mutableListOf<Int>()

    while (leftIndex < left.size && rightIndex < right.size) {
        if (left[leftIndex] <= right[rightIndex]) {
            result.add(left[leftIndex])
            leftIndex++
        } else {
            result.add(right[rightIndex])
            rightIndex++
        }
    }

    while (leftIndex < left.size) {
        result.add(left[leftIndex])
        leftIndex++
    }

    while (rightIndex < right.size) {
        result.add(right[rightIndex])
        rightIndex++
    }

    return result.toTypedArray()
}

fun main() {
    val arr = arrayOf(38, 27, 43, 3, 9, 82, 10)
    println("정렬 전 : ${arr.joinToString(", ")}")

    val sortedArr = mergeSort(arr)

    println("정렬 후 : ${sortedArr.joinToString(", ")}")
}

// 정렬 전 : 38, 27, 43, 3, 9, 82, 10
// 정렬 후 : 3, 9, 10, 27, 38, 43, 82

 

먼저 배열을 더 이상 나눌 수 없을 때까지 재귀적으로 배열을 2개의 하위 배열로 나눈다. 이 과정에서 mergeSort()가 재귀 호출되며 arr.size / 2 때문에 배열이 계속 반으로 나뉘어지게 된다.

이후 배열이 더 이상 2로 나눌 수 없을 정도로 작아지면(=배열 크기가 1이 되거나 배열이 빈 경우) 정렬된 배열을 하나의 배열로 병합한다. 병합할 때는 두 배열에서 가장 작은 값을 차례로 비교해서 새 배열에 추가한다. 그리고 재귀 호출이 완료되면 병합된 배열들이 점점 큰 배열로 다시 병합되서 최종적으로 정렬된 배열을 얻게 된다.

메인 함수의 입력값을 바탕으로 어떻게 작동하는지 확인하면 아래와 같이 작동한다.

 

• 1번째 호출 : [38, 27, 43] / [3, 9, 82, 10]
• 2번째 호출 : [38] / [27, 43] / [3, 9] / [82, 10]
• 3번째 호출 : [38], [27], [43], [3], [9], [82], [10]

 

3번만에 배열에 값 하나씩만 들어있도록 나눠졌다. 크기가 1인 배열은 정렬된 상태라고 간주하기 때문에 이제 병합이 실행된다.

병합 단계에서 중요한 것은 병합할 두 배열이 모두 정렬된 상태여야 한다는 것이다.

 

• [38], [27], [43]은 하나의 요소만 있는 배열이므로 이미 정렬된 상태다. 38과 27, 43은 서로 다른 배열에 있었고 27과 43이 든 배열은 각각 정렬된 상태기 때문에 [27], [43]을 병합해서 [27, 43]이 된다
• 이후 [38]과 [27, 43]을 병합한다. 이 과정에서 아래의 비교 과정이 이뤄진다
  • 27 < 38 -> [27]
  • 38 -> [27, 38]
  • 43 -> [27, 38, 43]

 

이것으로 왼쪽 배열의 정렬이 끝났으니 오른쪽 배열인 [3, 9, 82, 10]의 분해, 병합이 시작된다. 분해 과정은 위의 3단계 호출에서 적었으니 생략하고 병합 과정을 확인한다.

 

• [3, 9]는 이미 정렬된 상태다 -> [3], [9]를 병합해서 [3, 9]의 배열 생성
• [82, 10]은 [82], [10]으로 나눠진다
  • 10 < 82 -> [10] 배열 생성
  • 82를 추가 -> [10, 82] 배열로 확장됨
• [3, 9]와 [10, 82] 배열 비교
  • 두 배열은 각각 정렬된 상태기 때문에 하나로 합친다 -> [3, 9, 10, 82] 배열로 확장됨

 

이제 2가지 배열이 생겼다. 왼쪽 배열은 [27, 38, 43]이고 오른쪽 배열은 [3, 9, 10, 82]다. 이제 두 배열을 병합한다.

두 배열을 병합하는 것은 서로 비교해서 더 작은 값을 차례로 새 배열에 추가한다. 이 때 두 배열의 인덱스를 써서 현재 비교 중인 위치를 추적한다. 결과는 처음엔 빈 배열이며, 예제 코드에서도 result가 빈 리스트로 초기화된 걸 볼 수 있다.

 

• 3 < 27 -> true -> 빈 리스트에 3 추가 -> [3]
  • 왼쪽 배열 : [27, 38, 43]
  • 오른쪽 배열 : [9, 10, 82]
  • 오른쪽 배열 인덱스 0에서 1로 증가 -> 3을 비교했기 때문에 다음 요소인 9를 비교
• 9 < 27 -> true -> 리스트에 9 추가 -> [3, 9]
  • 왼쪽 배열 : [27, 38, 43]
  • 오른쪽 배열 : [10, 82]
  • 오른쪽 배열 인덱스 1에서 2로 증가 -> 9를 비교했기 때문에 다음 요소인 10을 비교
• 10 < 27 -> [3, 9, 10]
  • 왼쪽 배열 : [27, 38, 43]
  • 오른쪽 배열 : [82]
  • 오른쪽 배열 인덱스 2에서 3으로 증가
• 27 < 82 -> [3, 9, 10, 27]
  • 왼쪽 배열 : [38, 43]
  • 오른쪽 배열 : [82]
  • 왼쪽 배열 인덱스 0에서 1로 증가
• 38 < 82 -> [3, 9, 10, 27, 38]
  • 왼쪽 배열 : [43]
  • 오른쪽 배열 : [82]
  • 왼쪽 배열 인덱스 1에서 2로 증가
• 43 < 82 -> [3, 9, 10, 27, 38, 43]
  • 왼쪽 배열 : []
  • 오른쪽 배열 : [82]
  • 왼쪽 배열 인덱스 2에서 3으로 증가
  • 그러나 왼쪽 배열은 모두 소진됨
• 남은 요소인 오른쪽 배열의 82를 result에 추가 -> [3, 9, 10, 27, 38, 43, 82]가 결과로 출력됨

 

이해가 안 된다면 중단점을 걸고 디버깅으로 실행해서 공책에 예상한 다음 동작과 실제 다음 동작을 비교해서 적어가며 확인해 본다. 위에 적은 내용들은 전체 작동 순서를 적은 게 아니라 생략된 부분이 있다.

 

힙 정렬

 

https://en.wikipedia.org/wiki/Heapsort

Heapsort - Wikipedia

힙 정렬은 비교 기반 정렬 알고리즘으로 올바른 데이터 구조를 사용한 선택 정렬의 구현이라고 볼 수 있다. 선택 정렬처럼 힙 정렬은 입력을 정렬된 영역, 정렬되지 않은 영역으로 나누고 여기서 가장 큰 요소를 추출해 정렬된 영역에 삽입하는 방식으로 반복해서 비정렬된 영역을 축소한다. 선택 정렬과 달리 힙 정렬은 비정렬 영역을 선형 시간으로 스캔해서 시간을 낭비하지 않고 힙 데이터 구조에서 정렬되지 않은 영역을 유지해서 각 단계에서 가장 큰 요소를 효율적으로 찾는다. 대부분 시스템에서 잘 구현된 퀵 정렬보다 다소 느리지만 구현이 매우 간단하고 최악의 경우 O(n log n) 런타임이 더 유리하단 이점이 있다. 대부분의 경우 실제 퀵 정렬 변형에는 퀵 정렬이 성능 저하를 감지할 경우 대비책으로 힙 정렬을 구현하는 게 포함된다
힙 정렬은 제자리 정렬 알고리즘이지만 안정적 정렬은 아니다...(중략)...힙 정렬 알고리즘은 힙 구성, 힙 추출의 2단계로 나눌 수 있다. 힙은 정렬할 객체의 배열을 넘어서는 공간을 차지하지 않는 암시적 데이터 구조로 배열은 각 배열 요소가 노드고 각 노드의 부모, 자식 링크가 배열 인덱스에서 간단한 산술로 정의되는 완전한 이진 트리로 해석된다...(중략)...첫 단계에선 데이터에서 힙이 만들어진다. 2번째 단계에선 힙에서 가장 큰 요소(힙의 루트)를 반복 제거해서 배열 끝에 배치함으로써 힙을 정렬된 배열로 바꾼다. 힙 속성을 유지하기 위해 힙은 제거될 때마다 업데이트된다
힙에서 모든 객체가 제거되면 그 결과는 정렬된 배열이 된다. 힙 정렬은 일반적으로 제자리에서 수행된다. 첫 단계에서 배열은 정렬되지 않은 접두사와 힙 정렬된 접미사(처음엔 비어 있음)로 나뉜다. 각 단계는 접두사를 축소하고 접미사를 확장한다...(중략)...힙 정렬 알고리즘은 배열을 이진 최대 힙으로 재배열하는 것으로 시작한다. 그 다음 힙의 루트(힙에 남아있는 가장 큰 요소)를 마지막 요소와 반복 교체한 다음 정렬된 접미사의 일부로 선언한다. 그 다음 루트를 교체해서 손상된 힙을 복구해 가장 큰 요소가 다시 루트에 오게 한다. 힙에 하나만 남을 때까지 이 과정이 반복된다...(중략)

무작위 값의 배열을 정렬하는 힙 정렬 실행

 

힙 정렬도 병합 정렬과 같이 비교 기반 정렬 알고리즘이다. 그러나 힙이라는 용어가 자주 나오는데 이 용어를 알려면 이진 트리와 우선순위 큐를 알아야 한다. 두 가지 개념만으로도 하나의 포스팅이 나올 정도로 양이 많기 때문에, 여기선 생략하고 추후 포스팅한다.

힙 정렬은 아래 단계를 거쳐 작동한다고 볼 수 있다.

 

• 힙 구성 : 주어진 배열을 힙 구조로 바꾼다. 일반적으로 최대 힙을 사용한다
• 정렬 : 힙의 가장 큰 요소(루트 요소)를 배열의 마지막 요소와 교환하고, 나머지 요소로 다시 힙을 구성하길 반복한다

 

아래는 코틀린으로 힙 정렬을 구현한 예시다.

 

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) {
        // 루트 노드를 배열의 마지막 요소와 교환
        swap(arr, 0, i)

        // 남은 요소로 다시 힙 구성
        heapify(arr, i, 0)
    }
}

/* 힙 구성 함수 */
fun heapify(arr: IntArray, n: Int, i: Int) {
    var largest = i // 현재 루트
    val left = 2 * i + 1 // 왼쪽 자식
    val right = 2 * i + 2 // 오른쪽 자식

    // 왼쪽 자식이 루트보다 큰 경우
    if (left < n && arr[left] > arr[largest]) {
        largest = left
    }

    // 오른쪽 자식이 현재까지의 최대값보다 큰 경우
    if (right < n && arr[right] > arr[largest]) {
        largest = right
    }

    // 루트가 최대값이 아닌 경우
    if (largest != i) {
        swap(arr, i, largest) // 루트와 최대값을 교환
        heapify(arr, n, largest) // 교환된 자식 노드로 재귀 호출
    }
}

fun swap(arr: IntArray, i: Int, j: Int) {
    val temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

fun main() {
    val arr = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    println("정렬 전 : ${arr.joinToString(", ")}")
    heapSort(arr)
    println("정렬 후 : ${arr.joinToString(", ")}")
}

// 정렬 전 : 64, 34, 25, 12, 22, 11, 90
// 정렬 후 : 11, 12, 22, 25, 34, 64, 90

 

for문을 써서 배열을 최대 힙으로 구성하는데, 이 과정에선 배열 중간 지점에서 시작해 루트 노드로 올라가며 heapify()를 호출한다. 이후 최대 힙이 완성되면 가장 큰 요소를 배열의 마지막 요소와 교환한다. 그 다음 힙 크기를 줄이고 다시 heapify()를 호출해 새로운 힙을 구성한다.

heapify()에선 현재 루트 노드 i에서 시작해 왼쪽과 오른쪽 자식을 계산한다. 왼쪽 자식이 현재 루트보다 크면 largest를 왼쪽 자식으로 업데이트하고 오른쪽 자식도 같은 방식으로 비교한다. 루트가 최대값이 아니면 루트와 최대값을 스왑하고 교환된 자식 노드로 heapify()를 재귀 호출해서 힙 속성을 유지한다.

 

힙 정렬의 작동 원리는 아래와 같다.

 

• 힙 구성 : 주어진 배열을 최대 힙으로 바꿔서 부모 노드가 자식 노드보다 크도록 설정한다
• 정렬
  • 최대 힙의 루트 노드(가장 큰 값)을 배열 끝으로 보내고 나머지 배열을 힙 구조로 변환한다
  • 이걸 반복하다 보면 최종적으로 모든 요소가 정렬된 배열을 얻는다

 

힙 정렬의 시간 복잡도는 최악, 평균, 최선의 경우 모두 O(n log n)으로 동일하며, 공간 복잡도는 추가적인 저장 공간이 필요없이 제자리에서 정렬하기 때문에 O(1)이다.

어째서 시간 복잡도는 모든 경우에 O(n log n)인가? 배열을 힙으로 구성하는 과정에서 각 요소의 힙 속성을 유지하기 위해 heapify()를 호출하는데, 이 작업은 구성 과정에서 모든 요소를 한 번씩 확인하기 때문에 총 O(n) 시간에 걸쳐 수행된다. 이후 정렬 과정에서 루트를 배열 끝으로 이동시키고 나머지 요소로 다시 힙을 구성하는 과정을 반복하는데, 각 요소를 루트에서 제거하는 과정은 O(log n) 시간에 걸쳐 이뤄진다. 왜냐면 힙의 깊이가 log n에 해당하기 때문이다.

따라서 n개의 요소에 대해 이 과정을 반복하면 O(n log n)의 시간이 소요된다.