삽입 정렬
지난 글: [알고리즘] - 선택 정렬
삽입 정렬(insertion sort)은 수열의 왼쪽부터 순서대로 정렬하는 방식이다. 작업하다 보면 좌측에는 정렬이 끝난 숫자가 오게 되고 우측에는 아직 확인하지 않은 숫자가 남게 된다. 우측의 미탐색 영역에서 숫자를 하나 꺼네서 정렬이 끝난 영역의 적절한 위치에 삽입해 나가는 방식이다.
1
5 3 4 7 2 8 6 9 1여기서 1부터 9까지의 숫자를 정렬해보자. 처음에는 왼쪽 끝의 숫자(5)를 정렬이 끝났다고 간주한다. 즉 5만 정렬된 상태가 된다.
2
계속해서 아직 작업하지 않은 (미탐색 영역) 숫자 중에서 왼쪽 끝에 있는 숫자(3)를 꺼내서 왼쪽에 있는 작업이 끝난 숫자와 비교한다. 왼쪽의 숫자가 크면 두 개의 숫자를 바꾼다. 이 작업을 자신보다 작은 숫자가 나타나거나 왼쪽 끝에 도착할 때가지 반복한다.
5 3 4 7 2 8 6 9 1
---------이 경우 5 > 3이므로 숫자를 교체한다.
3 5 4 7 2 8 6 9 1
---------숫자(3)가 왼쪽 끝에 도착했으므로 여기서 멈춘다. 숫자 3을 작업이 끝난 것으로 간주한다. 3과 5가 정렬되고 우측에 있는 나머지 7개 숫자가 미탐색 영역이 된다.
3
다음은 3라운드다. 같은 방식으로 미탐색 영역의 왼쪽 끝(4) 숫자를 꺼내서 왼쪽에 있는 숫자와 비교한다.
3 5 4 7 2 8 6 9 1
---------5 > 4 이므로 숫자를 교체.
3 4 5 7 2 8 6 9 1
---------3 4 5 7 2 8 6 9 1
---------3 < 4로 자신보다 작은 숫자가 나타났으므로 멈춘다. 숫자 4의 작업이 끝났다. 3, 4, 5가 정렬된 상태로 정렬 완료 영역이 넓어졌다.
4
같은 방식으로 모든 숫자가 정렬될 때까지 반복한다.
1 2 3 4 5 6 7 8 9모든 숫자의 정렬이 완료된다.
삽입 정렬에서는 각 라운드의 첫 숫자를 그 왼쪽에 있는 숫자와 비교한다. 앞서 본 것처럼 만약 왼쪽에 있는 숫자가 작다면 비교할 필요 없이 라운드를 종료한다. 교체가 발생하지 않는 것이다. 하지만 꺼낸 숫자가 정렬 완료 영역의 숫자보다 작을 때는 그 숫자가 가장 왼쪽에 도착할 때까지 비교와 교체 작업을 한다. 구체적으로는 k라운드에서 k-1회씩 작업한다. 최악의 경우 2라운드에서 1회, 3라운드에서 2회, ... , n라운드에서 n-1회 비교와 교체가 발생하므로 계산 시간이 버블 정렬이나 선택 정렬과 같이 O(n2)가 된다. 그리고 최악의 입력 데이터는 마찬가지로 역순(큰 순)으로 나열된 경우다.
참고 서적:
