'[Public] 컴퓨터공학/알고리즘'에 해당되는 글 13건

  1. 2010.05.12 [알고리즘] 삽입 정렬 (Insert Sort) (정렬#3) (10)
2010.05.12 11:30
(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 -> ] -> 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 ]   [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 삽입



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


장점으로는

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

가장 빠른 결과를 얻는다.


하지만

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



삽입 정렬은 이동하는데

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

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


자 그러면

어떻게 이해가 되었는가?




아직 이해가 어렵다면

다음 소스를 보아라




다음은

결과 이다.




글을 읽고 이해를 하였다면

리플 남겨주는 당신은 센스쟁이.... ^^
Posted by 차출발 차출발

댓글을 달아 주세요

  1. 검색하다가 2012.02.10 21:23  댓글주소  수정/삭제  댓글쓰기

    훌륭하네요. 다른 블로그에 틀리게 설명된것도 많았는데 정확하고 간결합니다.

  2. 123 2013.10.07 01:29  댓글주소  수정/삭제  댓글쓰기

    감사합니다. 덕분에 쉽게 이해했네요. 책도 이상하게 설명해서 헷갈렸던 차였습니다. ㅎㅎ

  3. BlogIcon ㅁㅇㄴㄹ 2014.06.10 05:11  댓글주소  수정/삭제  댓글쓰기

    감사합니다

  4. 강석렬 2015.03.10 21:15  댓글주소  수정/삭제  댓글쓰기

    잘 봤습니다 감사합니다~~^^

  5. BlogIcon 2015.04.17 15:39  댓글주소  수정/삭제  댓글쓰기

    님 대박이에요 잘 보고 갑니다!

  6. 부니 2015.10.04 11:11  댓글주소  수정/삭제  댓글쓰기

    코드에서 제일 밑에 pData[j+1]=temp;이 아니라 pData[j]=temp; 아닌가요?

  7. 어리보기 2016.02.25 17:06  댓글주소  수정/삭제  댓글쓰기

    좋은 글이네요.
    많은 도움이 되었습니다.

  8. 코딩마스터 2016.11.28 09:32  댓글주소  수정/삭제  댓글쓰기

    좋은글 감사합니다! 한번에 이해됬습니다 ㅎ_ㅎ

  9. 오렌지 2017.03.11 13:10  댓글주소  수정/삭제  댓글쓰기

    감사해요~ 정보 잘봤어요

  10. BlogIcon 알바 . 2017.12.05 20:12 신고  댓글주소  수정/삭제  댓글쓰기

    감사합니다