✔︎ 이 글은 Swift Algorithm Club 문서를 번역한 것입니다.
삽입 정렬
목표: 배열을 오름차순(혹은 내림차순)으로 정렬하기
숫자 배열이 주어지고, 이를 순서대로 정렬해야 한다. 이 때 삽입 정렬 알고리즘은 다음과 같이 작동한다.
-
숫자를 파일에 놓는다. 이 파일은 정렬되지 않은 상태다.
-
파일에서 숫자를 하나 뽑는다. 뽑는 숫자는 어떤거든 상관 없지만, 파일의 맨 위부터 뽑는 것이 가장 쉽다.
-
뽑은 숫자를 새 배열에 추가한다.
-
정렬되지 않은 파일에서 새 숫자를 뽑아 앞선 새 배열에 추가한다. 이 숫자는 처음 뽑았던 숫자 앞과 뒤에 모두 올 수 있으며, 이를 통해 두 숫자는 정렬되게 된다.
-
파일에서 새 숫자를 뽑아 배열의 알맞은 위치에 배치해 정렬한다.
-
파일에 숫자가 없을 때까지 반복한다. 파일은 비게 되고, 배열은 정렬된다.
파일에서 숫자를 뽑아 배열의 알맞은 위치에 추가해 정렬하기 때문에 이를 "삽입"정렬이라고 부른다.
예시
정렬해야 하는 수가 [ 8, 3, 5, 4, 6] 이라 해 보자. 이는 우리가 가진 정렬되지 않은 파일이다.
처음 숫자 8 을 뽑아서 새 배열에 추가한다. 배열엔 아무것도 없으므로 쉽게 할 수 있다. 정렬된 배열은 [ 8 ] 이 되고, 파일은 [ 3, 5, 4, 6 ] 이다.
파일에서 다음 숫자인 3 을 뽑아서 정렬된 배열에 추가한다. 이는 8 앞으로 가야 하고, 배열은 [ 3, 8 ] 이 되고, 파일은 [ 5, 4, 6 ] 으로 줄어든다.
다음 숫자 5 를 뽑아 배열에 추가한다. 이는 3 과 8 사이에 들어간다. 정렬된 배열은 [ 3, 5, 8 ] , 파일은 [ 4, 6 ] 이다.
파일이 빌 때까지 이 프로세스를 반복한다.
제자리 정렬(In-place sort)
*In-place sort : 추가적인 메모리 공간이 거의 안 드는 정렬*
위에서 한 설명은 정렬되지 않은 파일과 정렬된 숫자를 담는 두 배열을 필요로 하는 것처럼 보인다.
하지만 분리된 배열을 만들지 않고 제자리에서 삽입 정렬을 할 수 있다. 단지 배열의 어떤 부분이 정렬됐고, 어떤 부분이 정렬되지 않았는지 잘 따라가기만 하면 된다.
초기에 배열은 [ 8, 3, 5, 4, 6 ] 이고, | 바는 정렬된 부분이 끝나고 파일이 시작되는 부분을 표현한다.
[| 8, 3, 5, 4, 6 ]이는 정렬된 배열이 비어 있고, 파일이 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 |]각 과정에서 | 바는 한칸씩 움직인다. 위에서 볼 수 있듯, | 앞의 부분은 항상 정렬돼있다. 왼쪽에 정렬되지 않은 숫자가 없이 파일이 빌 때까지 파일은 줄어들고, 정렬된 배열은 하나씩 늘어난다.
어떻게 추가하나
매 단계마다 정렬되지 않은 파일에서 맨 앞 숫자를 뽑아 정렬된 배열의 적절한 위치에 추가한다. 그 수를 알맞은 곳에 넣어 배열의 시작이 정렬된 상태로 있도록 만든다. 이게 어떻게 동작할까?
우리가 몇 가지 요소를 정렬했고, 그래서 배열의 상태가 아래와 같다고 가정하자.
[ 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 는 제 자리를 찾았고, 앞의 배열은 다시 정렬됐다.
이것은 다음 파트에서 보게 될 삽입 정렬의 내부 반복을 설명한 것이다. 교환을 통해 파일의 맨 처음 수를 정렬된 부분에 추가하게 된다.
코드
스위프트로 삽입 정렬을 구현한 코드는 다음과 같다.
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
}이 코드를 플레이그라운드에 넣고 다음과 같이 실행해보자.
let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(list)코드가 작동하는 방식은 다음과 같다.
- 배열의 복사본을 만든다. 매개변수
array를 직접적으로 바꿀 수 없기 때문에 이 작업이 필요하다. 스위프트가 가진sorted()와 같이,insertionSort()함수는 원래의 배열을 복사해 정렬한 것을 반환한다. - 이 함수에는 두 개의 반복문이 있다. 밖의 반복문은 배열의 각 요소에 대해서 적용되는 것으로, 파일에서 맨 앞 수를 뽑는 역할을 한다. 변수
x는 정렬된 부분의 끝이자 파일이 시작되는 인덱스(앞에서|바가 위치하는 곳)를 의미한다. 0부터x까지에 해당하는 배열의 앞 부분은 언제나 정렬돼야 한다는 걸 기억하자. 나머지,x부터 마지막 요소는 정렬되지 않은 파일이다. - 안의 반복문은
x위치에 있는 요소에 대해서 확인한다. 이는 파일의 맨 앞 숫자이고, 이는 자신의 앞 요소보다 작을 수 있다. 내부의 반복문은 정렬된 배열을 뒤에서부터 확인 해 나간다. 앞 숫자가 클 때마다 두 수를 교환한다. 내부의 반복문이 끝나면 배열의 앞 부분은 다시 정렬되고, 정렬된 부분의 요소는 하나 늘게 된다.
주의: 밖의 반복문은 0이 아닌 1 인덱스부터 시작한다. 파일에서 정렬된 부분으로 제일 처음 수를 옮기는 것은 아무 것도 바뀌지 않으므로 건너뛰어도 된다.
교환 멈춰!
위의 삽입 정렬도 잘 작동하지만, swap() 을 호출하지 않음으로써 조금 더 빠르게 바꿀 수 있다.
위에서 우리는 다음 요소를 정렬시키기 위해 숫자들을 교환했다.
[ 3, 5, 8, 4 | 6 ]
<-->
swap
[ 3, 5, 4, 8 | 6 ]
<-->
swap앞의 요소와 매번 교환하는대신, 모든 요소들을 한칸씩 오른쪽으로 옮기고, 정렬할 숫자를 해당 위치에 복사하는 것을 사용해보자.
[ 3, 5, 8, 4 | 6 ] 4 기억하기
*
[ 3, 5, 8, 8 | 6 ] 8을 오른쪽으로 옮기기
--->
[ 3, 5, 5, 8 | 6 ] 5을 오른쪽으로 옮기기
--->
[ 3, 4, 5, 8 | 6 ] 4를 해당 위치에 복사하기
*코드상에서 다음과 같이 나타낼 수 있다.
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] //1
currentIndex -= 1
}
sortedArray[currentIndex] = temp //2
}
return sortedArray
}//1 번 라인에서 앞의 요소들이 한칸씩 옮겨진다. 내부 반복문의 마지막에, y 가 새 숫자가 위치할 인덱스를 의미하고, //2 번 라인에서 이 숫자를 그 장소에 복사한다.
제네릭으로 만들어보자
*제네릭(generic) : 데이터 타입에 관계 없이 어떤 요소든 사용할 수 있도록 만드는 것(타입)*
숫자가 아닌 다른 것들도 정렬할 수 있으면 좋을 것이다. 배열의 데이터 타입을 제네릭으로 설정하고, 사용자 정의 함수(혹은 클로저)를 사용하여 < 비교 연산자의 기능을 만들 수 있다. 코드의 두 부분만 바꾸면 된다.
함수의 시그니처(정의)는 다음과 같이 바뀐다.
func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {배열은 [T] 형 배열이 되고, 이 때의 T 는 제네릭 타입을 담는다. 이제 insertionSort() 는 숫자, 스트링 등 어떤 타입의 배열이든 모두 처리할 수 있다.
새로운 매개변수 isOrderedBefore: (T, T) -> Bool 은 두 개의 T 객체를 인자로 받아 첫 번째 객체가 두 번째 객체 전에 위치하면 참을, 그렇지 않으면 거짓을 반환하는 함수이다. 이는 사실 스위프트의 sort() 함수가 하는 동작과 같다.
바뀔 다음 부분은 코드의 내부 반복문인데, 다음과 같이 바뀐다.
while y > 0 && isOrderedBefore(temp, a[y-1]) {temp < a[y - 1] 과 같이 쓰는 대신, isOrderedBefore() 함수를 호출하는 것이다. 이는 완벽히 동일한 동작을 하는데, 거기에 더해 숫자가 아닌 다른 어떤 객체든 비교할 수 있게 된다.
이를 플레이그라운드 상에서 다음과 같이 실행해보자.
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 에 따라 정렬하게 한다.
삽입 정렬은 안정 정렬이다. 정렬이 안정적이라는 것은, 같은 요소가 있을 때 정렬 전과 정렬 후 두 요소의 순서가 같다는 것을 의미한다. 이는 숫자나 스트링타입과 같은 단순한 값들에 대해서는 그다지 중요하지 않지만, 더 복잡한 것들에 대해서는 중요할 수 있다. 위의 예시에서 두 객체가 같은 priority 를 갖는다면, 각각의 다른 프로퍼티와 관련 없이 두 객체는 교환되지 않는다.
성능
삽입 정렬은 배열이 정렬돼있으면 정말 빠르다. 당연한 듯 들리겠지만, 모든 탐색 알고리즘이 그런 것은 아니다. 현실에서 많은 데이터는 전체적으로는 아니더라도, 일정 부분 정렬돼있으므로 삽입 정렬은 이 경우에 꽤 좋은 성능을 낸다.
최악의 경우, 그리고 평균적인 경우 삽입 정렬의 성능은 O(n^2) 이다. 함수에 두 개의 중첩된 반복문이 있기 때문이다. 퀵소트와 합병 정렬과 같은 다른 정렬 알고리즘에선 O(n log n) 의 시간복잡도를 갖는데, 이는 큰 수에 대해 더 빨리 동작할 수 있다.
삽입 정렬은 작은 배열을 정렬할 때 가장 빠르다. 몇몇 표준 라이브러리에선 파티션의 크기가 10 이하일 때 정렬 함수를 퀵소트에서 삽입 정렬로 바꾸어 사용하기도 한다.
스위프트의 내장된 sort() 함수와 insertionSort() 를 비교해봤다. 100개 정도의 요소가 들어 있는 배열에 대해서는 그 속도가 거의 차이가 없었다. 하지만, 배열의 크기가 커질수록 O(n^2) 가 O(n log n) 에 비해 훨씬 느려졌고, 삽입 정렬이 그 속도를 따라갈 수 없었다.
참고
Written for Swift Algorithm Club by Matthijs Hollemans
원문 https://github.com/raywenderlich/swift-algorithm-club/tree/master/Insertion%20Sort
