데이터를 정렬하는 방법은 여러가지가 있습니다. 선택 정렬은 실행될때 배열의 앞쪽 하위배열부터 정렬하기 시작하기 때문에 뒤 쪽의 하위배열은 건드리지 않습니다. 선택 정렬은 정렬되지 않은 바로 다음 하위배열을 탐색하여 이미 정렬된 하위배열에 추가할 것인지 넘어갈 것인지를 결정합니다.
Here's another way to think about sorting. Imagine that you are playing a card game. You're holding the cards in your hand, and these cards are sorted. The dealer hands you exactly one new card. You have to put it into the correct place so that the cards you're holding are still sorted. In selection sort, each element that you add to the sorted subarray is no smaller than the elements already in the sorted subarray. But in our card example, the new card could be smaller than some of the cards you're already holding, and so you go down the line, comparing the new card against each card in your hand, until you find the place to put it. You insert the new card in the right place, and once again, your hand holds fully sorted cards. Then the dealer gives you another card, and you repeat the same procedure. Then another card, and another card, and so on, until the dealer stops giving you cards.
이런 과정은 삽입 정렬의 기본 원리입니다. 삽입 정렬은 1번 인덱스 부터 시작하여 배열의 따라 루프하며 알맞는 자리를 찾는 방법입니다. 매번 탐색하는 새로운 값은 딜러가 건네는 새 카드이고 마찬가지로 하위 배열에서 알맞은 자리를 찾아 옆에 새 값을 삽입합니다. 이 과정을 아래에 그림으로 나타냈습니다.
인덱스 0부터 인덱스 5까지 이미 정렬된 하위 배열을 생각해 봅시다. 인덱스 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 라이선스를 적용합니다.