본문으로 바로가기

[Swift] Insertion Sort란?

category IOS 공부/알고리즘_Swift 2020. 9. 21. 23:28
728x90

목표는 배열을 내림차순 혹은 오름차순으롤 정렬하는 것이다!

숫자 배열을 받았는데, 순서에 맞게 정렬해야하는 상황이라고 쳐보자. Insertion sort 알고리즘은 아래와 같이 수행된다.

  • 숫자들을 pile(더미)에 쌓는다.(아직 정렬X)
  • pile에서 숫자를 꺼낸다. 어떤 것을 고르던 상관은 없으나, pile의 맨 위부터 뽑는게 가장 쉬운 방법이다.
  • 추출한 숫자를 새로운 배열에 넣는다.
  • 정렬되지 않은 pile에서 다음 숫자를 추출하고 또 새로운 배열에 넣는다. 해당 숫자는 맨 첫 번째에 추출한 숫자의 앞/뒤로 가서 이제 숫자가 정렬되게 되는 것이다.
  • 다시 추출하고, 위치에 맞게 배열 내에 넣어준다.
  • 이 과정을 정렬되지 않은 pile 내에 숫자가 다 사라질 때 까지 반복한다. 결과적으로 빈 pile과 정렬된 배열을 얻게 되는 것이다.

예를 들어서, [8,3,5,4,6] 배열에 대해서 생각해보자. 해당 배열이 정렬되지 않은 pile인 것이다.

먼저 첫 번째 숫자인 8을 추출해서 새로운 배열에 넣는다. 아직까지 배열에 아무것도 없어서 수월하다. 정렬된 배열은 현재 [8]이고 pile은 [3,5,4,6]이다.

다음 숫자인 3을 추출한다. 이는 8보다 앞에 와야 하기에, 정렬된 배열은 [3,8]이 되고, pile은 [5,4,6]으로 줄어들게 된다.

또 다음 숫자인 5를 추출해서 배열에 넣게 되면, 정렬된 배열은 [3,5,8]이고, pile은 [4,6]이 된다.

위 과정을 pile이 빈 공간이 될 때 까지 반복하면 된다.

 

In-place Sort

위의 방법은 두 개의 배열을 필요로 한다. 하지만, in-place 방식으로 수행하게 되면 새로운 배열을 만들어 정렬할 필요가 없다. 그냥 배열 내의 어느 부분이 이미 정렬되었는지, 아닌지를 트래킹하면 된다.

동일하게 초기 배열이 [8,3,5,4,6] 이라고 하자. |는 정렬된 부분과 pile의 시작 부분을 나누는 경계 역할을 한다.

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

지금은 정렬을 하지 않았기에, 정렬된 부분이 비어있고 pile을 8로 시작하는 것을 확인할 수 있다.
이후 첫 수행을 하게 되면 아래와 같은 형식의 배열을 얻게 된다.

[8|3,5,4,6]

정렬된 부분은 [8]이고 pile이 [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의 가장 앞 요소를 가져오고 있는 것을 볼 수 있다. 가져온 숫자를 적절한 위치에 배치해야 앞 배열이 정렬된 상태로 유지되게 된다.

만약 몇 단계를 거쳐서 아래의 배열을 얻었다고 해보자.

[ 3, 5, 8 | 4, 6 ]

다음에 넘어오게 될 숫자는 4이다. 해당 숫자를 [3,4,8] 배열에 알맞게 넣어야 하는 것이다. 한 가지 방법으로는 이전 요소(8)를 보는 것이다.

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

84보다 크다. 그러니 48의 앞에 와야한다. 그렇기에 두 숫자를 바꿔준다.

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

아직 끝난게 아니다. 또 새로운 이전의 요소인 5가 등장했다. 이는 4보다 크기에 두 숫자를 바꿔준다.

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

또 다시 이전의 요소인 3을 보면, 4보다 크지 않기에 정렬이 잘 되었다는 것을 알 수 있다.

이는 insert sort 알고리즘의 내부 구조를 설명한 것이다. 즉 이전 요소들과 하나하나 비교하고 바꿔가면서 제 위치를 찾아가는 방식인 것이다.

어떤 식으로 이루어지고, 수행되는지 이해했으니 이제 코드로 봐보자.

 

Code

insertion sort를 구현해보자.

func insertionSort(_ array: [Int]) -> [Int] {
    var sortedArray = array
    for index in 1..<sortedArray.count {
        var currentIndex = index
        while currentIndex > 0 && sortedArray[currentIndex] < sortedArray[currentIndex - 1] {
            sortedArray.swapAt(currentIndex - 1, currentIndex)
            currentIndex -= 1
        }
    }
    return sortedArray
}

테스트 코드도 실행해보자.

var list = [1,4,2,10,3,6,8,7]
insertionSort(list) // [1, 3, 5, 6, 7, 10, 26]

코드가 어떻게 돌아가는지 한 번 봐보자.

  1. 먼저 배열을 복사한다. 왜냐하면 직접적으로 기존 배열의 요소들을 수정할 수 없기 때문에 복사는 필수적이다. 기존 Swift의 sort()insertionSort() 함수도 원래 배열의 복사본을 정렬해서 반환해준다.
  2. 위 함수에는 두 가지 루프가 있다. 바깥 루프(for문)의 경우는, 기존 배열에서 순차적으로 하나하나 보는 역할을 한다. |의 위치(인덱스)를 x라고 했을 때, 0부터 x 까지는 정렬된 배열이고, x부터 마지막 요소까지는 정렬되지 않은 pile에 해당하는 것이다.
  3. 내부 루프는 요소들의 위치를 본다. pile의 맨 앞 숫자를 가ㅣㅈ고 와서, 이전의 요소와 비교하여 작은지를 본다. 내부 루프는 정렬된 배열을 거꾸로 단계적으로 이동한다. 매번 이전 숫자가 큰지 확인하고 서로의 위치를 바꾼다. 내부 루프가 끝나게 되면, 정렬된 배열은 하나 더 추가된 상태로 늘어나게 된다.

인덱스가 0이 아닌 1부터 시작하는 것은, 맨 처음의 원소를 pile에서 정렬된 부분으로 옮기는 것은 아무것도 바꾸는 것이 없기에 스킵하는 것이 좋다.

 

Swap없이는 어떻게...?

위 버전의 insertion sort는 잘 작동하나, swap( )을 제거함으로써 조금 더 빠르게 만들 수 있다. 위에서 경우는 숫자들이 swap되며 정렬되었던 것을 볼 수 있다.

이전 요소들과 swapping하는 것 대신에, 요소들을 오른쪽으로 이동시킨 후, 복사한 새 값을 적합한 위치에 놓는다.

[ 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 sortedArray = array
    for index in 1..<sortedArray.count {
        var currentIndex = index
        let temp = sortedArray[currentIndex] // 복사
        while currentIndex > 0 && temp < sortedArray[currentIndex - 1] {
            sortedArray[currentIndex] = sortedArray[currentIndex - 1] // 이전 요소들 우측 이동 
            currentIndex -= 1
        }
        sortedArray[currentIndex] = temp // 복사한 값 붙여넣기
    }
    return sortedArray
}

 

조금 더 사용성 좋게...!

위 경우는 Int에 대해서만 적용이 가능하다. 이제는 데이터 형태에 관여받지 않고 일반적으로 사용할 수 있게 만들어보자. 코드 2줄만 수정하면 된다.

func insertionSort<T>(_ array: [T], _ isOrderedBefore : (T,T) -> Bool) -> [T] {
    var sortedArray = array
    for index in 1..<sortedArray.count {
        var currentIndex = index
        let temp = sortedArray[currentIndex] // 복사
        while currentIndex > 0 && isOrderedBefore(temp, sortedArray[currentIndex - 1]) {
            sortedArray[currentIndex] = sortedArray[currentIndex - 1] // 이전 요소들 우측 이동 
            currentIndex -= 1
        }
        sortedArray[currentIndex] = temp // 복사한 값 붙여넣기
    }
    return sortedArray
}

배열 타입인 [T]T는 placeholder 타입이다. 이제 insertionSort()에 숫자,문자 등 이외의 것들로 구성된 배열이 입력될 수 있다는 것이다. 그리고 새로운 파라미터인 isOrderedBefore(T,T) -> Bool 함수는 두 개의 T 객체를 받아서 첫 번째 객체가 두 번째 객체 앞에 오면 true를, 두 번째 객체가 첫 번째 객체 앞에 와야 한다면 false를 반환한다. 즉 앞의 T가 뒤의 T보다 순서적으로 앞서있어야 한다는 것이다.

그리고 내부 루프에서 while의 조건을 isOrderedBefore(temp, sortedArray[currentIndex - 1])로 바꿔주면 된다. temp < sortedArray[currentIndex-1]대신 써준 것이다. 기능은 동일하다.

Playground에서는 아래와 같이 사용할 수 있다. <>로 정렬 순서(오름차순/내림차순)를 정해준다.

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

물론 문자열에도 적용이 가능하며, 더 복잡한 객체들에 대해서도 적용이 가능하다.

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

클로져는 insertionSort()에게 priority에 따라 프로퍼티를 정렬하라고 시키는 역할이 되는 것이다.
문제는 두 개의 객체가 동일한 우선 순위를 가지고 있다면, 값의 형태에 관계 없이, 이 두 객체는 서로 swap 될 수 없다.

 

성능

Insertion sort는 이미 정렬된 배열에 대해 매우 빠르게 작동된다. 응? 당연한 말이다. 다만 데이터가 방대할 경우(전부 정렬이 되어있지는 않은 경우)에는 좋지 않다.

가장 최악의 경우인 insertion sort는 O(n^2)이다. 왜냐하면 두 개의 루프가 함수 안에 묶여서 구성되어 있기 때문이다. quicksort나 merge sort 같은 다른 정렬 알고리즘의 경우는 O(n log n) 성능을 보여 큰 데이터에도 보다 빠른 모습을 보인다.

insertion sort는 작은 배열을 정렬하는 데 빠르다. 데이터가 그렇게 크지 않다면 insertion sort와 다른 정렬 알고리즘의 성능은 큰 차이가 없을 것이지만 데이터가 늘어남에 따라 insertion sort는 다른 정렬 알고리즘의 성능을 따라갈 수 없을 것이다...!

 

 

끄읕.

'IOS 공부 > 알고리즘_Swift' 카테고리의 다른 글

[Swift] Binary Search란?  (0) 2020.12.23
[프로그래머스] 해쉬 - 위장  (0) 2020.12.19
[Swift] Insertion Sort란?  (0) 2020.09.21
[Swift] Queue란?  (0) 2020.09.17
[Swift] Stack이란?  (0) 2020.09.15
[Swift] Swift 값 입력, 비교  (0) 2020.09.03

댓글을 달아 주세요

var wrapper3 = document.getElementById('search-tag'); var myScroll3 = new IScroll(wrapper3, { click: false, mouseWheel: true, scrollbars: true, preventDefaultException:{tagName:/.*/}, disablePointer: true, disableTouch: false, disableMouse: false }); var btnMenu3 = document.getElementById('call-search'); btnMenu3.addEventListener('click', function(){ setTimeout(function(){ myScroll3.refresh(); }, 500); });