C
2005.08.10 10:02

삽입정렬 Insertion Sort

조회 수 31551 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

+ - Up Down Comment Print Files
?

단축키

Prev이전 문서

Next다음 문서

+ - Up Down Comment Print Files
이 첨부 파일에 있는 건 일반적인 함수의 형태이다. (int형 뿐 아니라 모든 형태의 자료형을 비교할 수 있도록 만든 것이다)
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.


■ 삽입 정렬 개념

삽입정렬은 매우 간단한 정렬 방법으로 소량의 자료를 처리하는데 유용
파일을 구성하고 있는 부파일(subfile)의 레코드들이 이미 정렬이 되어 있다고 가정
한 번에 한 개의 새로운 레코드를 입력하여 정렬되어 있는 사이트의 적당한 위치를 찾아서 레코드를 삽입
따라서 새롭게 삽입된 레코드를 포함하여 파일은 항상 정렬된 상태를 유지


■ 삽입 정렬 과정



  ① 두 번째 키를 기준으로 하여 첫 번째 키를 비교하여 키 값에 따라 순서대로 나열
  ② 세 번째 키를 기준으로 하여 두 번째 키와 첫 번째 키를 비교하여 키 값에 따라 순서대로 나열
  ③ 계속하여 n번째 키를 앞의 n-1개의 키와 비교하여 삽입될 적당한 위치를 찾아 삽입한다.

30 15 20 17 40 ------>  초기상태
30 15 20 17 40 ------>  15 이전의 수를 비교해서 15 < 30 이므로 삽입
15 30 20 17 40 ------>  20 이전 수만 비교. 20 < 30 이므로 삽입
15 20 30 17 40 ------>  17 이전 수만 비교. 17 < 20 이므로 삽입
15 17 20 30 40 ------>  40 이전수 비교. 삽입은 없음
15 17 20 30 40 ------>  정렬완료



■ 삽입 정렬 알고리즘
-----------------------------------------
procedure INSERT(R,n)
     for j ← 2 to n do
          R ← Rj
          K ← Kj
          i  ← j-1
          while i >0 and Ki > K do
               Ri+1 ← Ri
               i ← i-1
          end
          Ri+1 ← R
     end
end INSERT
-----------------------------------------


■ 성능
    ▷ 최적 - 입력 데이타가 정렬하고자 하는 순서대로 배열되어 있는 경우 최소 비교 횟수 : n-1
    ▷ 최악 - 입력 데이타가 역순으로 정렬되어 있는 경우 최대 비교 횟수 : (n(n-1))/2
    ▷ 각 패스별로 중간 정도에서 부분적인 정렬이 완료되었을 경우 평균 비교 횟수 : (n(n-1))/4
    ▷ n개의 레코드를 정렬할 때 n-1번 삽입이 발생되어 전체 수행시간 : O(N2)

■ 메모리 사용 공간

    ▷별도의 기억 공간을 필요로 하지 않기 때문에, 리스트의 크기 만큼의 기억 공간이 있으면 됨
       즉, n개의 레코드 크기만큼의 기억 공간이 있으면 됨

■ 특징
    ▷ 간단하며, 안정적
    ▷ 적은 비교와 많은 교환이 필요한 방법 - 작은 레코드 배열에 가장 유리
    ▷ 순서가 틀린 레코드의 순서가 전체 레코드 수에 비해 현저하게 적은 경우 효율적
        즉, 원시리스트가 부분적으로 정렬되어 있는 경우에 효과적
    ▷ 전체 레코드 수가 20~25 이하인 경우 가장 빠른 정렬 기법
    ▷ 매회 서브파일 크기 증가

Dreamy의 코드 스크랩

내가 모으고 내가 보는

List of Articles
번호 분류 제목 날짜 조회 수 추천 수
30 MFC CString을 유니코드로 변환 WCHAR에 저장하는 방법 1 2006.04.14 54735 0
29 MFC 다이얼로그 기반 APP에서 Edit에 엔터키 먹게 하기 2006.04.14 40830 0
28 일반 아스키 코드표 file 2006.01.04 41442 0
27 MFC MFC에서 인자(argument)처리 2005.10.28 45645 0
26 C Base64 로 encoding / decoding 하는 예제 file 2005.09.22 24798 0
25 C 64bit DES 암복호화 코드 1 file 2005.09.22 31309 0
24 일반 cmd.exe 명령 도움말 2005.08.31 30670 0
23 C 병합 정렬 Merge Sort file 2005.08.10 34004 0
22 C 힙 정렬 Heap Sort file 2005.08.10 36674 0
21 C 퀵 정렬 Quick Sort file 2005.08.10 37301 0
20 C 쉘 정렬 Shell Sort file 2005.08.10 31859 0
19 C 거품정렬 Bubble Sort file 2005.08.10 31349 0
» C 삽입정렬 Insertion Sort file 2005.08.10 31551 0
17 C 선택정렬 Selection Sort file 2005.08.10 32753 0
16 C Queue 큐 (Linked List로 구현) file 2005.08.10 40825 0
목록
Board Pagination ‹ Prev 1 ... 27 28 29 30 31 32 33 Next ›
/ 33

나눔글꼴 설치 안내


이 PC에는 나눔글꼴이 설치되어 있지 않습니다.

이 사이트를 나눔글꼴로 보기 위해서는
나눔글꼴을 설치해야 합니다.

설치 취소

Designed by sketchbooks.co.kr / sketchbook5 board skin

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5