목표는 배열을 내림차순 혹은 오름차순으롤 정렬하는 것이다!
숫자 배열을 받았는데, 순서에 맞게 정렬해야하는 상황이라고 쳐보자. 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 ]
^8은 4보다 크다. 그러니 4는 8의 앞에 와야한다. 그렇기에 두 숫자를 바꿔준다.
[ 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]코드가 어떻게 돌아가는지 한 번 봐보자.
- 먼저 배열을 복사한다. 왜냐하면 직접적으로 기존 배열의 요소들을 수정할 수 없기 때문에 복사는 필수적이다. 기존 Swift의
sort()나insertionSort()함수도 원래 배열의 복사본을 정렬해서 반환해준다. - 위 함수에는 두 가지 루프가 있다. 바깥 루프(for문)의 경우는, 기존 배열에서 순차적으로 하나하나 보는 역할을 한다.
|의 위치(인덱스)를x라고 했을 때, 0부터x까지는 정렬된 배열이고,x부터 마지막 요소까지는 정렬되지 않은 pile에 해당하는 것이다. - 내부 루프는 요소들의 위치를 본다. 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는 다른 정렬 알고리즘의 성능을 따라갈 수 없을 것이다...!
끄읕.