목표: 배열을 낮은 순서에서 높은 순서로(또는 높은 순서에서 낮은 순서로) 정렬한다.
숫자로 이루어진 배열이 주어졌을 때, 이를 올바른 순서로 정렬해야 한다. 삽입 정렬 알고리즘은 다음과 같이 동작한다:
이것이 "삽입" 정렬이라고 불리는 이유다. 더미에서 숫자를 하나씩 꺼내서 배열의 적절한 정렬된 위치에 삽입하기 때문이다.
정렬할 숫자가 [ 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 ]이다.
더미가 빌 때까지 이 과정을 반복한다.
위 설명은 두 개의 배열이 필요한 것처럼 보인다. 하나는 정렬되지 않은 배열이고, 다른 하나는 정렬된 숫자를 담는 배열이다.
하지만 별도의 배열을 만들지 않고도 제자리 정렬을 수행할 수 있다. 배열의 어느 부분이 이미 정렬되었고, 어느 부분이 정렬되지 않은 배열인지 추적하기만 하면 된다.
초기 배열은 [ 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 ]
^
8이 4보다 큰가? 그렇다. 따라서 4는 8 앞에 위치해야 한다. 이 두 숫자를 교환하면 다음과 같다:
[ 3, 5, 4, 8 | 6 ]
<-->
교환
아직 끝나지 않았다. 새로운 이전 요소인 5도 4보다 크다. 이 두 숫자도 교환한다:
[ 3, 4, 5, 8 | 6 ]
<-->
교환
다시 이전 요소를 살펴본다. 3이 4보다 큰가? 아니다. 이제 4에 대한 작업이 완료되었다. 배열의 시작 부분이 다시 정렬된 상태가 되었다.
이 과정은 삽입 정렬 알고리즘의 내부 루프를 설명한 것이다. 다음 섹션에서 이 알고리즘을 더 자세히 살펴볼 것이다. 이 루프는 정렬되지 않은 부분의 가장 위에 있는 숫자를 정렬된 부분에 삽입하기 위해 숫자를 교환하는 방식으로 동작한다.
다음은 Swift로 구현한 삽입 정렬 코드이다:
func insertionSort(_ array: [Int]) -> [Int] {
var sortedArray = array // 1
for index in 1..<sortedArray.count { // 2
var currentIndex = index
while currentIndex > 0 && sortedArray[currentIndex] < sortedArray[currentIndex - 1] { // 3
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 파라미터의 내용을 직접 수정할 수 없기 때문에 이 과정이 필요하다. Swift의 sorted() 함수와 마찬가지로 insertionSort() 함수도 원본 배열의 정렬된 복사본을 반환한다.
이 함수 안에는 두 개의 루프가 있다. 외부 루프는 배열의 각 요소를 차례대로 확인한다. 이 루프는 정렬되지 않은 부분에서 가장 위에 있는 숫자를 선택한다. currentIndex 변수는 정렬된 부분의 끝과 정렬되지 않은 부분의 시작 지점( | 막대의 위치)을 나타낸다. 기억해야 할 점은, 어떤 순간이든 배열의 처음부터 currentIndex까지는 항상 정렬되어 있다는 것이다. 나머지 부분, 즉 currentIndex부터 마지막 요소까지는 정렬되지 않은 부분이다.
내부 루프는 currentIndex 위치에 있는 요소를 확인한다. 이 요소는 정렬되지 않은 부분의 맨 위에 있는 숫자이며, 이전 요소들보다 작을 수 있다. 내부 루프는 정렬된 배열을 거꾸로 순회하며, 더 큰 숫자를 찾을 때마다 두 숫자의 위치를 바꾼다. 내부 루프가 완료되면 배열의 처음 부분이 다시 정렬되고, 정렬된 부분이 하나의 요소만큼 증가한다.
참고: 외부 루프는 인덱스 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에 있는 줄은 이 숫자를 올바른 위치에 복사한다.
숫자뿐만 아니라 다른 타입도 정렬할 수 있으면 좋을 것이다. 배열의 데이터 타입을 일반화하고, 사용자가 제공한 함수(또는 클로저)를 사용해 비교 연산을 수행할 수 있다. 이를 위해 코드를 두 부분만 수정하면 된다.
함수 시그니처는 다음과 같이 바뀐다:
func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {배열은 [T] 타입을 가지며, T는 제네릭을 위한 플레이스홀더 타입이다. 이제 insertionSort()는 숫자, 문자열, 기타 객체 등 어떤 타입의 배열도 받을 수 있다.
새로운 매개변수 isOrderedBefore: (T, T) -> Bool은 두 T 객체를 받아 첫 번째 객체가 두 번째 객체보다 앞에 오면 true를 반환하고, 그렇지 않으면 false를 반환하는 함수다. 이는 Swift의 내장 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 이하일 때 퀵 정렬에서 삽입 정렬로 전환하는 정렬 함수를 제공한다.
insertionSort()와 Swift의 내장 sort() 함수를 간단히 비교해 보았다. 약 100개 정도의 배열에서는 속도 차이가 거의 없었다. 그러나 입력 크기가 커질수록 **O(n^2)**는 **O(n log n)**에 비해 급격히 성능이 떨어지며, 삽입 정렬은 따라잡을 수 없다.
Swift 알고리즘 클럽을 위해 Matthijs Hollemans가 작성