데이터를 정렬하는 방법은 여러가지가 있습니다. 선택 정렬은 실행할때 배열의 앞쪽 하위배열부터 정렬하기 시작하기 때문에 뒤 쪽의 하위배열은 건드리지 않습니다. 선택 정렬은 정렬되지 않은 바로 다음 하위배열을 탐색하여 이미 정렬된 하위배열에 추가할 것인지 넘어갈 것인지를 결정합니다.
정렬을 한번 다르게 생각해봅시다. 어떤 사람이 카드 게임을 하고 있다고 상상해보세요. 손에 카드를 쥐고 있고 이미 정렬되어있는 상태입니다. 딜러가 새로운 카드 한 장을 건네줍니다. 그럼 이제 이 카드를 또 정렬하는 수고를 하지 않도록 새 카드를 한 번에 올바른 위치에 끼워 넣을 것입니다. 선택 정렬에서는 이미 정렬된 하위 배열에 새로이 추가되는 요소가 이 정렬된 하위 배열에 있는 요소보다 더 작지는 않습니다. 하지만 바로 위의 카드 예시에서 새로운 카드는 이미 정렬된 카드에 있는 것보다 값이 작을 수도 있습니다. 따라서 카드를 흝어보면서 새 카드와 손에 쥐고 있는 카드를 일일이 비교할 것입니다. 이렇게 새 카드를 알맞은 자리에 집어넣으면 쥐고 있는 카드 덱은 이미 잘 정렬된 상태입니다. 딜러가 또 다른 카드를 주면 이와 같은 과정을 반복합니다. 그다음 카드도 마찬가지로, 딜러가 더는 줄 카드가 없을 때까지 이 과정을 반복하게 됩니다.
이런 과정은 삽입 정렬의 기본 원리입니다. 삽입 정렬은 1번 인덱스 부터 시작하여 배열의 따라 순환하며 알맞은 자리를 찾는 방법입니다. 매번 탐색하는 새로운 값은 딜러가 건네는 새 카드이고 마찬가지로 하위 배열에서 알맞은 자리를 찾아 옆에 새 값을 삽입합니다. 이 과정을 아래에 그림으로 나타냈습니다.
인덱스 0번부터 55 번까지 이미 정렬이 되어있는 하위 배열을 생각해 봅시다. 인덱스 6번에 있는 요소를 이 정렬된 하위 배열에 끼워 넣어서 인덱스 0번부터 6번까지 정렬되도록 해야 합니다. 아래 그림을 보세요:
정렬이 끝났을 때는 하위 배열이 다음과 같이 되어야 합니다.
6번 위치에 있는 한 요소를 그 왼쪽 하위 배열 안에 삽입하기 위해 반복적으로 바로 왼쪽의 요소들과 비교하며 움직입니다. 6번 위치에 있는 이 요소를 key 라고 부릅시다. 이 key가 그 왼쪽에 있는 요소보다 크기가 작다고 판단되면 key가 그 비교 대상 요소 왼쪽에 와야 한다는 것을 알고 있으므로 해당 요소를 오른쪽으로 한 칸 움직입니다. 이를 구현하기 위해 두 가지를 알아야 합니다. 첫째로 요소를 오른쪽으로 한 칸 움직일 수 있는 slide 기능이 있어야 하고, 둘째로 key가 그 바로 왼쪽에 있는 요소로 치환되지 않도록 이 key를 보관하는 분리된 공간이 필요합니다. 이 예제에서는 인덱스 6 번 위치에 있는 요소를 key 변수로 끌어옵시다.
이제 key를 5번 위치에 있는 요소와 비교해봅시다. key (5) 는 5번 위치에 있는 요소 (13) 보다 값이 작으므로 이 요소를 6번 위치로 옮겨야 합니다.
slide 명령은 요소를 복사하여 오른쪽으로 한 칸 옆에 놓습니다. 그 다음 이 key를 4번 위치에 있는 요소와 비교합니다. 비교해 보았더니 key (5)는 4번 위치에 있는 요소 (10) 보다 작아서 이 요소를 옆으로 보냅니다.
이제 key를 3번 위치의 요소와 비교했더니 더 커서 요소를 오른쪽으로 보냅니다.
2번 위치의 요소에서도 마찬가지로 같은 일이 일어납니다:
이제 1번 위치 요소 (3) 까지 왔습니다. 이 요소는 key보다 작으므로 오른쪽으로 보내지 않아도 됩니다. 이번에는 요소를 오른쪽으로 보내는 대신에 key를 이 요소의 오른쪽에 오도록 삽입합니다 (2번 위치로 오게끔). 결과적으로 인덱스 0 부터 6 까지 있는 하위 배열은 모두 올바르게 정렬되었습니다.
삽입 정렬은 어떤 요소를 왼쪽의 정렬된 하위 배열 안으로 반복적으로 삽입합니다. 처음에는 인덱스 0 만이 존재하는 하위 배열이 정렬되었다고 볼 수 있습니다. 하지만 이런 배열은 요소가 한 개뿐이므로 사실 정렬되었다고 보기는 힘듭니다. 예제를 한번 풀어봅시다. 초기 배열이 다음과 같이 주어졌습니다.
인덱스 0 번만 존재하는 하위 배열이 주어졌으므로 첫 번째 key는 인덱스 1 번에 있습니다. (이제부터 정렬된 하위 배열은 빨간색으로, key는 노란색으로, 아직 정렬되지 않은 배열은 파란색으로 표시하겠습니다.) 이제 key를 왼쪽에 정렬된 하위 배열로 삽입합니다.
방금 정렬된 하위 배열은 인덱스가 0 번부터 1 번까지 있으며 새로운 key는 인덱스 2 번에 있습니다. 이 key를 왼쪽에 정렬된 하위 배욜 속으로 삽입해 봅시다.
각 배열 요소를 차례대로 key로 삼고 이를 정렬된 하위 배열의 왼쪽에 삽입하는 과정을 계속합니다.
마지막으로 배열의 가장 오른쪽에 있는 요소를 삽입하면 배열 전체의 정렬이 끝나게 됩니다.
사실 앞에서 다룬 예제는 방금보다는 조금 더 자세하게 들어다볼 필요가 있습니다. Key를 삽입할 때 이보다 왼쪽에 있는 모든 요소의 값이 더 작을 경우 (2번 키와 3번 키를 삽입했을 때)와 왼쪽의 요소 보다 크거나 같을 경우 (13번 key를 삽입했을 때)로 나눠서 생각해봐야 합니다. 전자의 경우 key 왼쪽에 있는 하위 배열의 모든 요소는 오른쪽으로 한 칸씩 움직이며 배열의 왼쪽 끝에 다다르면 멈춰야 합니다. 후자의 경우, key를 바로 왼쪽의 요소와 비교를 할 때 이미 왼쪽의 모든 요소가 정렬되었다고 판단되어 요소는 움직이지 않게 되고 key는 시작한 위치로 되돌아가게 됩니다.

정렬된 하위 배열에 값 삽입하기

삽입 정렬의 주요 단계는 배열에 key 변수에 저장된 값을 넣기 위한 공간을 만드는 것입니다. 위에서 보았듯이 삽입 정렬은 key의 초기 위치에서 왼쪽에 있는 하위 배열을 오른쪽에서 왼쪽으로 가면서 key 보다 값이 더 큰 요소를 오른쪽으로 하나씩 밀어가면서 정렬합니다. key보다 값이 작거나 key와 값이 같은 요소를 찾으면 밀기를 중단하고 key를 이 요소 오른쪽 빈 공간에 붙여넣습니다. (물론 이 위치는 실제로 빈 공간이 아니고 그 자리에 있던 요소가 오른쪽으로 한 칸 움직인 것입니다.) 아래 그림으로 이해해봅시다.

위 자료는 다트머스 대학교 컴퓨터공학과토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.
로딩 중