Insertion Sort with Swift

Insertion Sort 는, 단순한 Sorting Algorithms 중 경우에 따라 비교적 빠를 수 있는 Algorithm 입니다. 

특히 대부분이 이미 정렬되어있는 경우 O(n) 까지 빨라질 수 있는데요, 그 원리를 하나하나 알아보겠습니다.

 

Example 1

첫 예시는 다른 Sorting 의 예시들처럼 아래 행렬을 가지고 차례차례 순서를 밟아보겠습니다.

 

[4,3,5,2,1]

1. 첫번째 element 인 4 를 먼저 하나의 상자에 넣습니다.

[4]
[4, 3, 5, 2, 1]

 

2. 두번째 element 인 3 과 상자에 있는 수(4) 를 비교합니다. 3이 더 작으므로, 상자 안에 3을 넣을 때 상자의 앞쪽에 넣습니다.

[3, 4]
[3, 4, 5, 2, 1]

 

3. 상자 [3, 4] 와 그 다음에 오는 element 5 를 비교합니다. 5 는 상자 뒤 끝 수 (가장 높은 수) 보다 높으므로, 상자의 뒤쪽 끝에 넣습니다.

[3, 4, 5]
[3, 4, 5, 2, 1]

 

4. 상자 [3, 4, 5]와 다음 element 2 를 비교합니다. 5 부터 2 와 비교하기 시작했을 때, 2 는 5, 4, 3 보다 작으므로 상자의 앞쪽 끝에 넣습니다. 

[2, 3, 4, 5]
[2, 3, 4, 5, 1]

이제 숫자가 1 하나 남았습니다.

5. 위 방식과 동일하게, 상자 뒤쪽 수들과 비교하며 적당한 위치를 찾아서 넣습니다. 

 

[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

Insertion Sorting 이 끝났습니다!

 

처음 배열 [4, 3, 5, 2, 1] 은 초기 상태가 거의 sorting 되지 않았기 때문에 5 를 상자에 넣는 과정 외에는 Bubble Sort, Selection Sort 와 과정의 수에 차이가 거의 없었음을 볼 수 있습니다.

 

 

Example 2

이제 거의 Sorting 되어있는 배열과 비교해보겠습니다.

 

[2,3,4,5,1]

 

1. 처음으로, 2 를 먼저 상자에 넣습니다.

[2]
[2, 3, 4, 5, 1]

 

2. 다음 수 (3) 와 상자 내의 element (2) 값을 비교합니다. 다음 수가 상자의 수 (2) 보다 크므로, 상자의 뒤쪽 끝에 위치시킵니다.

[2, 3]
[2, 3, 4, 5, 1]

 

3. 다음 수 (4) 와 상자 내의 뒤쪽 끝 element (3) 을 비교합니다. 다음 수가 상자 뒤쪽 끝 수보다 크므로, 상자의 뒤쪽 끝에 위치시킵니다.

[2, 3, 4]
[2, 3, 4, 5, 1]

 

4. 다음 수 (5) 와 상자 내의 뒤쪽 끝 element (4) 을 비교합니다. 다음 수가 상자 뒤쪽 끝 수보다 크므로, 상자의 뒤쪽 끝에 위치시킵니다.

[2, 3, 4, 5]
[2, 3, 4, 5, 1]

 

5.  다음 수 (1) 와 상자 내의 뒤쪽 끝 element (5) 을 비교합니다. 이번에는 다음 수가 더 작습니다. 상자의 다른 값들과도 차례로 비교합니다.

5 > 1

4 > 1

3 > 1

2 > 1 

1 을 상자의 적당한 위치 ( 앞쪽 끝) 에 위치시킵니다.

[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

Insertion Sort 가 종료되었습니다 !

 

두번째 예제에서는, 앞 4 개의 수가 모두 이미 정렬되어있었고, 따라서 한번씩만 비교를 하고 정렬을 시켜주었습니다.

만약 [1, 2, 3, 4, 5] 를 Insertion Sort 시킨다고 한다면, 총 4 번의 과정만 거치면 정렬이 완료됩니다. ( O(n) )

 

 

 

 

Implementation

이제, Swift Code 로 Insertion Sort 를 만들어보겠습니다. 

func insertionSort(arr: [Int]) -> [Int] {
    if arr.count == 0 { return arr }
    
    var box : [Int] = [arr[0]]
    var toBeCompared : Int
    
    for i in 1 ..< arr.count {
        toBeCompared = arr[i]
        
        boxLoop: for boxIndex in 0 ..< box.count {
            
            if box[box.count - 1 - boxIndex] < toBeCompared {
                box.insert(toBeCompared, at: box.count - 1 - boxIndex + 1)
                break boxLoop
            }
            
            if boxIndex == box.count - 1 {
                box.insert(toBeCompared, at: 0)
            }
        }
    }
    
    return box
}

위 코드에서 설명과 다르게 보이는 것은 target Array 가 변하지 않는 것 입니다. insertionSort funtion 은 box 를 return 하기 때문에 기존 input array 의 변화 없이 box 만 값을 순서대로 추가시켜줍니다. 또한, 'boxLoop' 는 쓰이지 않아도 전혀 지장이 없지만, 내부 for statement 에서 나갈 때 혼동이 없도록 표기하였습니다. 

 

 

box 는 새로 만들어나가서 마지막에 return 될 array ('상자') 이며

toBeCompared (비교대상) 는 box 내 값들과 비교 후 box 에 삽입될 값을 의미합니다.

 

 

1. 처음에 함수가 호출되면, empty array 가 아닌지 확인합니다. (arr.count == 0 ) 

2. box 에 하나의 element arr[0] 을 갖는 [Int] 를 대입합니다.

3. 첫번째 for statement 의 index 'i' 는 toBeCompared 의 index 에 대한 것입니다. ( 1, 2, ... arr.count - 1 )

4. 두번째 for statement는 box 내 elements 와 toBeCompared 를 차례대로 (box 의 뒤쪽 element 부터 앞쪽까지) 비교하는 곳입니다. 

5. 두번째 for statement 에서, toBeCompared 가 box 내 어떤 값보다 크다면 그 값의 뒤쪽에 삽입 후 boxLoop 를 종료합니다.

6. 두번째 for statement 에서, toBeCompared 가 box 내 모든 값보다 크지 않다면, box 의 가장 앞에 삽입합니다. (boxIndex 가 boxLoop 의 마지막 값이므로 boxLoop 를 자동으로 종료하게 됩니다.) 

7. 해당 과정을 끝까지 (target Array 의 index 마지막까지) 반복한 후 생성된 box 를 return 합니다.

 

 

[4, 3, 5, 2, 1] array 를 이용해서 insertionSort function 을 테스트 해보았습니다.

let testArr = [4,3,5,2,1]

func insertionSort(arr: [Int]) -> [Int] {
    if arr.count == 0 { return arr }
    
    var count = 0
    var box : [Int] = [arr[0]]
    var toBeCompared : Int
    print("target Array: \(arr)\n")
    for i in 1 ..< arr.count {
        toBeCompared = arr[i]
        print("box: \(box)\n")
        boxloop: for boxIndex in 0 ..< box.count {
            count += 1
            print("compare \(box[box.count - 1 - boxIndex]) with \(toBeCompared)")
            if box[box.count - 1 - boxIndex] < toBeCompared {
                
                box.insert(toBeCompared, at: box.count - 1 - boxIndex + 1)

                break boxloop
            }
            
            if boxIndex == box.count - 1 {
                box.insert(toBeCompared, at: 0)

            }
        }
    }
    print("box: \(box)")
    print("count :\(count)")
    return box
}

insertionSort(arr: testArr)

//target Array: [4, 3, 5, 2, 1]
//
//box: [4]
//
//compare 4 with 3
//box: [3, 4]
//
//compare 4 with 5
//box: [3, 4, 5]
//
//compare 5 with 2
//compare 4 with 2
//compare 3 with 2
//box: [2, 3, 4, 5]
//
//compare 5 with 1
//compare 4 with 1
//compare 3 with 1
//compare 2 with 1
//box: [1, 2, 3, 4, 5]
//count :9

위와 같은 코드로 실험을 진행했을 때, target Array 가 [4, 3, 5, 2, 1] 일 때는 9번, [2, 3, 4, 5, 1] 일 때는 7번 비교한다는 것을 알 수 있습니다. 

 

array 의 크기가 커질수록 차이는 커지게 되고 크기를 9 로 한다고 하면 

[1,2,3,4,5,6,7,8,9] 으로 정렬을 시행했을 때는 8번, ( best case) 

[2,3,4,5,6,7,8,9,1] 으로 정렬을 시행했을 때는 15번,

[9,8,7,6,5,4,3,2,1] 으로 정렬을 시행했을 때는 36번 비교하게 됩니다. (worst case)