삽입 정렬(Insertion Sort)

[최종 수정일 : 2017.05.20]

원문 : https://github.com/raywenderlich/swift-algorithm-club/tree/master/Insertion%20Sort

삽입 정렬(Insertion Sort)

목표 : 배열을 낮은 것부터 높은 것으로 정렬합니다. (또는 높은 것을 낮은 것으로)

숫자들의 배열을 올바른 순서로 넣어야 합니다. 삽입 정렬 알고리즘은 다음과 같이 동작합니다.

• 숫자들을 쌓아(pile) 놓습니다. 이러한 무더기(pile)는 정렬되지 않았습니다.
• 무더기(pile)에서 숫자를 선택합니다. 어떤것을 선택하는지는 중요하지 않지만, 무더기에서 맨 위를 선택하는게 가장 쉽습니다.
• 새로운 배열에 이 숫자를 삽입합니다.
• 정렬되지 않은 무더기(pile)에서 다음 숫자를 선택하고 새로운 배열에 삽입합니다. 처음에 선택한 첫번째 숫자 앞이나 뒤로 보내며, 이제 두 숫자들은 정렬되어 있습니다.
• 다시한번 무더기(pile)에서 다음 숫자를 선택하고 배열에 적절하게 정렬된 위치로 삽입합니다.
• 무더기(pile)에 더이상 숫자가 없을때까지 이 작업을 계속합니다. 비어 있는 무더기(pile)로 끝나고 배열은 정렬되어 있습니다.

무더기(pile)에서 숫자를 가져와서 배열에 적절히 정렬된 위치로 넣기 때문에 삽입(insertiion)정렬 이라고 합니다.

예제(An Example)

정렬한 숫자는 [8, 3, 5, 4, 6]입니다. 이것은 우리의 정렬되지 않은 무더기(pile) 입니다.

첫번째 숫자 8을 선택하고 새로운 배열에 삽입합니다. 아직 배열에는 아무것도 없기에 쉽습니다. 정렬된 배열은 이제 [8]이고 무더기(pile)는 [3, 5, 4, 6]입니다.

무더기(pile)에서 다음 숫자 3을 선택하고 정렬된 배열에 삽입합니다. 그것은 8의 앞으로 가야하며, 정렬된 배열은 이제 [3, 8]이고 무더기(pile)는 [5, 4, 6]이 남아있습니다.

무더기(pile)에서 다음 숫자 5을 선택하고 정렬된 배열에 삽입합니다. 그것은 3과 8 사이로 가야합니다. 정렬된 배열은 [3, 5, 8] 이고 무더기(pile)는 [4, 6]입니다.

무더기(pile)이 빌때까지 이 과정을 반복합니다.

제자리로 정렬(In-place sort)

위의 설명은 두개의 배열이 필요한 것으로 보입니다: 하나는 정렬되지 않은 무더기(pile)이고 하나는 정렬된 숫자를 포함하고 있습니다.

별도의 배열을 만들필요 없이, 제자리(in-place)로 삽입 정렬을 수행할 수 있습니다. 배열의 어느 부분이 이미 정렬되어 있고 어떤 부분이 정렬되지 않은 무더기(pile)인지 추적합니다.

초기 배열은 [8, 3, 5, 4, 6]입니다. |바는 정렬된 마지막 위치와 무더기(pile)의 시작을 보여줍니다.

[| 8, 3, 5, 4, 6 ]

이것은 정렬된 부분이 비어있고, 무더기(pile)가 8에서 시작한다는 것을 보여줍니다.

첫번째 숫자를 처리한 후에 다음처럼 됩니다.

[ 8 | 3, 5, 4, 6 ]

정렬된 위치는 [8]이고 무더기는 [3, 5, 4, 6]입니다. | 바는 오른쪽으로 한칸 이동되었습니다.

정렬하는 동안 배열의 내용이 변경되는 방법 입니다.

[| 8, 3, 5, 4, 6 ]
[ 8 | 3, 5, 4, 6 ]
[ 3, 8 | 5, 4, 6 ]
[ 3, 5, 8 | 4, 6 ]
[ 3, 4, 5, 8 | 6 ]
[ 3, 4, 5, 6, 8 |]

각 단계에서, | 바는 한칸씩 이동합니다. 보시다시피, 배열의 시작 부분까지 |는 항상 정렬됩니다. 무더기(pile)가 비어있고 더 이상 정렬되지 않은 숫자가 없을때까지, 무더기(pile)가 하나씩 줄어들고 정렬된 위치가 하나씩 커집니다.

삽입하는 방법(How to insert)

각 단계에서 정렬되지 않은 무더기(pile)에서 최상위 숫자를 선택하고 배열의 정렬된 위치에 삽입합니다. 배열의 시작부분부터 정렬되도록 해당 번호를 적절한 위치에 두어야 합니다. 어떻게 동작하나요?

이미 처음 몇가지 요소들을 수행했고 배열이 다음과 같이 보입니다:

[ 3, 5, 8 | 4, 6 ]

다음에 정렬할 번호는 4입니다. 그것을 정렬된 위치 [3, 5, 8]에 삽입해야 합니다. 다음과 같이 한가지 방법이 있습니다. : 이전 요소 8을 보세요.

[ 3, 5, 8, 4 | 6 ]
        ^

4보다 큰가요? 네 그렇습니다, 4는 8앞에 옵니다. 이러한 두 숫자들을 교환합니다.

[ 3, 5, 4, 8 | 6 ]
        <-->
       swapped

아직 끝나지 않았습니다. 새로운 이전 요소 5는 4보다 큽니다. 이러한 두 숫자들을 교환합니다.

[ 3, 4, 5, 8 | 6 ]
     <-->
    swapped

다시한번, 이전 요소를 봅니다. 3이 4보다 크나요? 아니요, 그렇지 않습니다. 그것은 4가 끝났다는 의미입니다. 배열의 시작 부분이 다시 정렬됩니다.

이것은 삽입 정렬 알고리즘의 내부 반복문에 대한 설명이었으며, 다음 섹션(section)에서 보게 될 것입니다. 숫자를 바꿔서 무더기(pile) 맨 위의 숫자를 정렬된 부분에 삽입합니다.

코드(The code)

Swift에서 삽입 정렬 구현은 다음과 같습니다.

func insertionSort(_ array: [Int]) -> [Int] {
  var a = array                             // 1
  for x in 1..<a.count {                    // 2
    var y = x
    while y > 0 && a[y] < a[y - 1] {        // 3
      swap(&a[y - 1], &a[y])
      y -= 1
    }
  }
  return a
}

플레이그라운드에 이 코드를 넣고 다음과 같이 테스트 하세요.

let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(list)

다음은 코드 동작 방법입니다.

1. 배열의 복사본을 만듭니다. 이것은 array 매개변수의 내용을 직접 수정할수 없기 때문에 필요합니다. Swift의 sort()와 마찬가지로 insertionSort() 함수는 원본 배열의 정렬된 복사본을 반환합니다.
2. 이 함수 안쪽에는 두개의 반복문이 있습니다. 바깥쪽 반복문은 배열의 각 요소들을 차례로 봅니다. 이것은 무더기(pile)에서 최상위 번호를 선택하는 것입니다. 변수 x는 정렬된 위치의 끝이 어디인지에 대한 인덱스이고 무더기(pile)의 시작 위치입니다(|바의 위치). 배열(인덱스 0에서 x까지)의 시작부분은 항상 정렬되어 있다는 것을 기억하세요. 나머지는 x인덱스에서 마지막 요소까지 정렬되지 않은 무더기(pile) 입니다.
3. 내부 반복문은 x위치의 요소를 봅니다. 이것은 무더기의 맨 위에 있는 숫자이고 이전 요소들 중 어떤 것보다 작을수 있습니다. 내부 반복문은 정렬된 배열을 거꾸로 이동합니다. 더 큰 이전 숫자를 찾을때마다 그것들을 교환합니다. 내부 반복문이 완료될때, 배열의 시작부분은 다시 정렬되고, 정렬된 위치는 하나의 요소만큼 증가합니다.

주의
바깥쪽 반복문은 0이 아니라 인덱스 1부터 시작합니다. 첫번째 요소를 정렬된 부분으로 옮기는 것은 실제로 아무것도 변경하지 않기에, 그것을 건너 뛸수도 있습니다.

더 이상 교체하지 않음(No more swaps)

위의 삽입 정렬 버젼은 잘 동작하지만, swap() 호출을 제거함으로써 더 빠르게 만들 수 있습니다.

다음 요소를 정렬된 위치로 이동하기 위해 숫자를 서로 바꾼것을 보았습니다.

[ 3, 5, 8, 4 | 6 ]
        <-->
        swap
        
[ 3, 5, 4, 8 | 6 ]
     <-->
     swap

이전의 각 요소들로 교체하는 대신에, 모든 요소를 한쪽에서 오른쪽으로 이동하고 나서 새로운 숫자를 오른쪽으로 복사 할 수 있습니다.

[ 3, 5, 8, 4 | 6 ]   remember 4
           *

[ 3, 5, 8, 8 | 6 ]   shift 8 to the right
        --->
        
[ 3, 5, 5, 8 | 6 ]   shift 5 to the right
     --->
     
[ 3, 4, 5, 8 | 6 ]   copy 4 into place
     *

다음과 같은 코드입니다.

func insertionSort(_ array: [Int]) -> [Int] {
  var a = array
  for x in 1..<a.count {
    var y = x
    let temp = a[y]
    while y > 0 && temp < a[y - 1] {
      a[y] = a[y - 1]                // 1
      y -= 1
    }
    a[y] = temp                      // 2
  }
  return a
}

//1이 있는 줄은 첫번째 요소들을 한칸씩 위로 이동시킵니다. 내부 반복문의 끝에 y는 정렬된 부분의 새 숫자에 대한 목적지 인덱스 이고, //2가 있는 줄은 이 숫자를 복사하는 곳입니다.

제네릭으로 만들기(Making it generic)

숫자 이외에 다른 것들을 정렬하는게 좋을 것입니다. 배열의 제너릭 데이터 타입을 만들고 더 작은지(less-than) 비교를 수행하려면 사용자 제공(user-supplied) 함수(또는 클로져)를 사용할 수 있습니다. 이것은 오직 코드를 두번 변경하면 됩니다.

함수의 용법(signature)은 다음과 같습니다.

func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {

배열은 [T] 타입을 가지며 여기서 T는 제네릭에 대한 견본 타입입니다. 이제 insertionSort()는 숫자, 문자, 그외 것들을 포함한 모든 종류의 배열에서 허용될 것입니다.

새로운 매개변수 isOrderdBefore: (T, T) -> Bool은 두개의 T객체를 가지고 첫번째 객체가 두번째 앞으로 오면 true를 반환하고, 두번째 객체가 첫번째 앞으로 오면 false를 반환하는 함수입니다. 이것은 Swift의 내장된 sort()함수와 정확히 같습니다.

유일한 다른 변경부분은 내부 반복문에 있으며, 이제 다음과 같이 됩니다.

      while y > 0 && isOrderedBefore(temp, a[y - 1]) {

temp < a[y -1]를 작성하는 대신에 insOrderedBefore()함수를 호출하였습니다. 그것은 숫자가 아닌 모든 종류의 객체를 비교할수 있다는 점만 제외하면, 정확히 같습니다.

플레이그라운드에서 이것을 테스트 하려면 다음과 같이 하세요

let numbers = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(numbers, <)
insertionSort(numbers, >)

<와 >은 정렬 순서를 결정하며, 각각 낮은곳에서 높은곳으로 그리고 높은곳에서 낮은곳으로 정렬합니다.

물론, 문자열과 같은 다른 것들을 정렬할 수 있습니다.

let strings = [ "b", "a", "d", "c", "e" ]
insertionSort(strings, <)

또는 훨씬 복잡한 객체도 정렬할 수 있습니다.

let objects = [ obj1, obj2, obj3, ... ]
insertionSort(objects) { $0.priority < $1.priority }

클로저는 insertionSort()가 객체의 priority프로퍼티를 정렬합니다.

삽입 정렬은 안정적인(stable) 정렬입니다. 정렬은 요소들이 정렬된 후에 상대적인 순서로 동일한 정렬 키가 남아있을때 안정적입니다. 이것은 숫자나 문자열처럼 간단한 값에는 중요하지 않지만, 더 복잡한 객체를 정렬 할때는 중요합니다. 위 예제에서, 두 객체들이 같은 priority를 가지면, 다른 프로퍼티의 값과 상관없이, 이러한 두 객체들의 주변을 교환하지 마세요.

성능(Performance)

이미 정렬된 배열이 있으면 삽입 정렬은 정말 빠릅니다. 그것이 분명하게 들리지만, 모든 검색 알고르짐에 대해서는 옳지(true) 않습니다. 실제로, 많은 데이터가 이미 크게 정렬되고(완전히 정렬된것 아니지만) 삽입 정렬은 그 경우에도 잘 동작합니다.

삽입 정렬의 성능은 최악의 경우와 평균적으로 O(n²⁾ 입니다. 이것은 함수안에 두개의 중첩된 반복문이 있기 때문입니다. 다른 정렬 알고리즘, 퀵 정렬(quicksort)과 결합 정렬(merge sort)은 O(n log n) 성능이며 큰(large) 입력에서 더 빠릅니다.

삽입 정렬은 작은 배열에 대해서 실제로 매우 빠릅니다. 일부 표준 라이브러리에서는 파티션의 크기가 10보다 작을때 퀵정렬에서 삽입 정렬로 교체하는 정렬 함수가 있습니다.

insertSort()와 Swift의 내장된 sort()를 비교하는 빠르기 테스트를 수행했었습니다. 약 100개의 항목의 배열에서 속도 차이는 작습니다. 하지만, 입력이 더 커지면, O(n²⁾ 는 O(n log n) 보다 훨씬 나빠지고, 삽입 정렬은 계속 유지할 수 없습니다.

이것도 보세요(See also)

위키피디아에 있는 삽입 정렬(Insertion sort on Wikipedia)