삽입 정렬
ko.khanacademy.org
삽입 정렬이란?
삽입 정렬은 1번 인덱스 부터 시작하여 배열을 따라 순환하며 알맞은 자리를 찾는 방법입니다. 매번 탐색하는 새 값은 딜러가 건네는 새 카드와 마찬가지입니다. 딜러에게 새 카드를 받고 전체 카드를 확인 후 알맞은 자리에 새 카드를 삽입합니다. 이 과정이 삽입 정렬입니다.
위 와 같이 5번 인덱스까지 정렬되어 있는 배열이 있습니다. 만약 인덱스 6번에 있는 요소를 이 정렬된 배열에 끼워 넣으려면 어떡해야할까요.
결과적으로 위 그림과 같이 돼야합니다. 6번에 위치한 요소를 왼쪽 하위 배열에 삽입하기 위해서 반복적으로 왼쪽의 요소들과 비교하며 움직여야합니다. 6번에 위치한 요소를 Key라고 부르겠습니다. 이 Key가 왼쪽에 있는 요소보다 크기가 작다고 판단되면 Key가 그 비교 대상 요소의 왼쪽에 와야한다는 것을 알고 있습니다. 그러므로 해당하는 요소를 오른쪽으로 한 칸 옮깁니다.
이를 구현하려면 어떤 기능이 필요할까요. 첫째로 요소를 오른쪽으로 한 칸 움직일 수 있는 slide 기능이 있어야 합니다. 둘째로 Key가 slide된 요소와 치환되지 않도록 따로 Key값을 보관하는 공간이 필요합니다.
이 예제에서는 인덱스 6번의 요소를 Key변수로 가져옵니다.
그리고 Key값을 5번 인덱스 요소와 비교합니다. Key는 5번 인덱스 요소(13)보다 값이 작으므로 5번 인덱스 요소를 6번 위치로 옮겨야합니다.
이어서 Key값을 4번 인덱스 요소와 비교합니다. 마찬가지로 Key값이 4번 인덱스 요소보다 작기 때문에 4번 인덱스 요소를 인덱스 5번에 위치시킵니다.
똑같은 방식으로 2번 인덱스 요소까지 위치를 바꿔줍니다.
이제야 1번 위치에 도달했습니다. 1번 인덱스 요소는 Key값보다 작기 때문에 오른쪽으로 slide할 필요가 없습니다. 대신에 Key값을 1번 인덱스의 오른쪽에 위치시키도록 합니다. 결과적으로 0번부터 6번 인덱스까지 정렬이 올바르게 됐습니다.
또 다른 예제
삽입 정렬은 어떤 요소를 왼쪽의 정렬된 하위 배열 안에 반복적으로 삽입합니다. 처음에는 인덱스 0 만이 존재하는 하위 배열이 있다고 볼 수 있습니다. 위 예제를 풀어보겠습니다.
인덱스 0 번만 존재하는 하위 배열이 주어졌기 때문에 인덱스 1번이 Key가 됩니다. 이제 Key를 왼쪽에 정렬된 하위 배열에 삽입합니다.
방금 정렬된 하위 배열이 0 번부터 1 번까지 있으므로 새로운 Key는 2번 인덱스가 됩니다. 연속해서 Key를 하위 배열에 삽입하겠습니다.
순서대로 배열을 정렬하고 마지막 6번 인덱스를 정렬하는 일만 남았습니다.
완료됐습니다. 조금 더 이 예제를 자세히 살펴보겠습니다. Key를 삽입 할 때 왼쪽에 있는 모든 요소의 값이 더 작을 경우와 왼쪽의 요소 보다 크거나 같을 경우로 나눠서 생각해야합니다. 전자의 경우 왼쪽의 하위배열의 모든 요소를 오른쪽으로 한칸씩 움직이며 Key가 배열의 왼쪽 끝에 다다르면 멈춥니다. 후자의 경우 Key를 바로 왼쪽과 비교할 때 이미 왼쪽의 모든 요소가 정렬되었다고 판단되어 요소는 움직이지 않고 Key는 원래 위치로 돌아갑니다.
요약
위 그림처럼 Key값보다 더 큰 요소를 오른쪽으로 하나씩 밀어가면서 정렬하고 Key값보다 작거나 같은 값인 인덱스 요소를 찾으면 그 인덱스의 오른쪽 빈 공간에 Key값이 들어가게됩니다.