[컴][알고리즘] insertion sort

정렬 알고리즘 / insertion sort / 삽입 정렬

목차

1. Insertion sort
2. quick sort
3. merge sort
4. heap sort

insertion sort

이것은 중간에 끼어넣는 insertion 을 이용한다.

ref. 1 의 움직이는 예제를 보면 이해가 쉽다. ref. 1 의 그림을 보면서 이 글을 보도록 하자.

일렬로 놓은 숫자박스가 있다고 생각하고, 그 숫자박스들을 순서대로 들어서 앞쪽으로 숫자크기에 맞게 정렬한다고 생각하면 된다.

어디다 insertion 을 하는가 하면 앞쪽으로 한다.
이때 앞쪽은 당연히 정렬되어 있어야 한다.
뒤쪽으로 해도 상관없을 듯

큰 녀석이 뒤로 오도록 정렬하자.

앞쪽에 insertion 을 하려면 첫번째 녀석은 의미가 없어서 두번째 녀석으로 시작한다.
두번째 녀석을 선택하고 앞쪽 녀석과. 비교한다.
앞쪽 녀석(첫번째)이 더 크면 앞쪽 녀석과 두번째 녀석을 바꾼다.

그 다음, 세번째 녀석을 가지고 비교를 시작한다.
앞의 녀석이 이미 정렬되어있으니 그냥 자기보다 작은 녀석이 나올 때까지 바꿔치면 된다.
그래서 selection sort 보다 write 이 많은 이유가 된다.

이렇게 swap 을 하는 것이 조금 간단한 방법이다.

원래는 이렇다.

앞쪽녀석들은 정렬되어 있으니 이 세번째 녀석이 들어갈 자리를 일단 찾자.
앞쪽의 녀석과 하나씩비교해서 현재값보다 작은 녀석이 "최초로 있는 곳"을 찾는다.
그곳 바로 옆에 세번째 녀석을 insertion 하면 된다.

insertion 을 하는 것은 당연히 그 녀석이 들어가는 위치 뒤의 녀석들을 뒤로 미는 것이라서 shifting 을 한다.
내 현재값의 인덱스의 앞쪽 녀석을 순차적으로 뒤로 옮긴다.
그리고 원하는 insertion 시점이 시프트되면 그만 시프트하고 거기에 값을 넣는다.
근데 이것을 줄이기 위해 만나기 전까지 계속 스왑한다.

See Also

1. Insertion Sort - GeeksforGeeks

Reference

1. http://en.wikipedia.org/wiki/Insertion_sort