[알고리즘] 삽입 정렬 (Insert Sort) (정렬#3)

(3 번째 정렬 Story)

삽입 정렬

이번엔 삽입 정렬이다.

삽입정렬의 방법은

이미 나열되어 있는 정렬할 공간에서
 
가장 작은 범위 부터 시작하여서

작은 범위 안에서 가장 작은 수가 나올때 까지

옆으로 이동하면서

마지막의 수를 이동한 자리의 빈공간에 넣어준다 하여

삽입 정렬이라 한다.

말로 설명하면 잘 모르니 그림을 보자




5 -> 1 -> 7 -> 4 -> 2 -> 6 -> 3

의 데이터를 정렬 할려고 한다.

 가장 작은 정렬 할 범위를 지정해주고 늘려가면서 진행된다.

먼저 시작점을 설정해야한다.

시작점을 0부터 하면 그 전 데이터가 없기 때문에

시작 점을 1부터 하고 진행한다.



자 그럼 정렬을 시작 해 보장


저장
[ 5 -> 1 ]-> 7 -> 4 -> 2 -> 6 -> 3   [1]저장

데이터 공간의 시작지점 1의 데이터 1을 저장해두고
범위 안에서 시작 보다 작은수를 이동한다..

이동
[ 5 -> 5 ]-> 7 -> 4 -> 2 -> 6 -> 3  [1]저장   (5 > 1)

5가 1보다 크므로 5의 데이터를 이동해준다

그리고 끝에 다가 오거나 저장된 수보다 작으면

이전에 저장 해 두었던 데이터를 빈 공간에 삽입해주는 것이다.

삽입
[ 1 -> 5 ]-> 7 -> 4 -> 2 -> 6 -> 3  저장된 1 삽입



이렇게 데이터 공간안에서 정렬이 완료 되면

데이터 공간을 하나씩 늘려 간다.


저장
[ 1 -> 5 -> 7 ] -> 4 -> 2 -> 6 -> 3   [7] 저장

스톱
[ 1 -> 5 -> 7 ] -> 4 -> 2 -> 6 -> 3   [7] 저장  (5<7)

삽입
[ 1 -> 5 -> 7 ] -> 4 -> 2 -> 6 -> 3   저장된 7을 삽입


방금은 정렬이 되어 있는 상태여서 원래 자리에 원래 값이 들어 갔다.

이해가 아직 안된 다면

 다음것을 보자.



저장
[ 1 -> 5 -> 7 -> 4 ] -> 2 -> 6 -> 3   [4] 저장

이동
[ 1 -> 5 -> 7 -> 7 ] -> 2 -> 6 -> 3   [4] 저장  (7 >4)

이동
[ 1 -> 5 -> 5 -> 7 ] -> 2 -> 6 -> 3   [4] 저장  (5 >4)

스톱
[ 1 -> 5 -> 5 -> 7 ] -> 2 -> 6 -> 3   [4] 저장 (1<4)

삽입
[ 1 -> 4 -> 5 -> 7 ] -> 2 -> 6 -> 3    저장되었던 4 삽입

이런 식으로 지속적으로 나아가면

저장
[ 1 -> 4 -> 5 -> 7 -> 2 ] -> 6 -> 3    [2] 저장

이동
[ 1 -> 4 -> 5 -> 7 -> 7 ] -> 6 -> 3    [2] 저장  (7>2)

이동
[ 1 -> 4 -> 5 -> 5 -> 7 ] -> 6 -> 3    [2] 저장  (5>2)

이동
[ 1 -> 4 -> 4 -> 5 -> 7 ] -> 6 -> 3    [2] 저장  (4>2)

스톱
[ 1 -> 4 -> 4 -> 5 -> 7 ] -> 6 -> 3    [2] 저장  (1<2)

삽입
[ 1 -> 2 -> 4 -> 5 -> 7 ] -> 6 -> 3    저장 된 2 삽입


- 다음 -

저장
[ 1 -> 2 -> 4 -> 5 -> 7  -> 6 ] -> 3   [6] 저장

이동
[ 1 -> 2 -> 4 -> 5 -> 7  -> 7 ] -> 3   [6] 저장    (7>6)

스톱
[ 1 -> 2 -> 4 -> 5 -> 7  -> 7 ] -> 3   [6] 저장    (5<6)

삽입
[ 1 -> 2 -> 4 -> 5 -> 6  -> 7 ] -> 3   저장된 6 삽입



- 다 음 -

저장
[ 1 -> 2 -> 4 -> 5 -> 6  -> 7  -> 3 ]   [3] 저장

이동
[ 1 -> 2 -> 4 -> 5 -> 6  -> 7  -> 7 ]   [3] 저장  (7 >3)

이동
[ 1 -> 2 -> 4 -> 5 -> 6  -> 6  -> 7 ]   [3] 저장  (6 >3)

이동
[ 1 -> 2 -> 4 -> 5 -> 5  -> 6  -> 7 ]   [3] 저장  (5 >3)

이동
[ 1 -> 2 -> 4 -> 4 -> 5  -> 6  -> 7 ]   [3] 저장  (4 >3)

스톱
[ 1 -> 2 -> 4 -> 4 -> 5  -> 6  -> 7 ]   [3] 저장  (2<3)

삽입
[ 1 -> 2 -> 3 -> 4 -> 5  -> 6  -> 7 ]  저장된 3 삽입



드디어 정렬이 완성 되었다.


장점으로는

만약 자료가 이미 정렬 되어 있을 경우에는

가장 빠른 결과를 얻는다.


하지만

정렬이 역순이면 최악의 복잡도가 나온다.



삽입 정렬은 이동하는데

오버헤드가 너무 크다는 단점을 지니고 있기 때문에.

상황에 맞는 정렬을 사용하기 바란다.


자 그러면

어떻게 이해가 되었는가?




아직 이해가 어렵다면

다음 소스를 보아라

다음은

결과 이다.

글을 읽고 이해를 하였다면

리플 남겨주는 당신은 센스쟁이.... ^^