삽입 정렬 (Insert Sort)

개념
첫번째 키는 정의된 것으로 보고 두번째 키부터 순서에 맞는 위치에 삽입시켜 정렬하는 방법

I. 삽입 정렬 (Insert Sort)의 개요

  가.  삽입 정렬의 정의

- 첫번째 키는 정의된 것으로 보고 두번째 키부터 순서에 맞는 위치에 삽입시켜 정렬하는 방법

 

나.  삽입 정렬의 특징

- 간단하지만 레코드의 이동이 많은 알고리즘

- 비교적 크기가 작은 데이터 집합 정렬에 유리함.

- 수행시간 복잡도: O(n2)

 

Ⅱ. 삽입 정렬의 단계 및 사례

     가.  삽입 정렬의 단계

- 삽입 대상 위치를 2번째부터 마지막까지 지정

- 비교 대상을 처음부터 바로 전까지 지정

- 정렬 대상의 값들과 뽑아낸 요소와 비교

- 삽입할 값보다 큰 값을 가진 모든 요소들을 한 자리씩 오른쪽으로 이동

- 새로 생긴 빈 자리에 해당 요소를 삽입

- 전체 데이터 집합의 정렬이 완료될 때까지 반복

 

     나.  삽입 정렬의 사례

void insertion_sort(element list[], int n) {

 int i, j;

 element next;

 for(i = 1; i < n; i++){

  next = list[i];

  for(j = i - 1; j >= 0 && next.key < list[j].key; j--){

   list[j + 1] = list[j];};

   list[j + 1] = next;

}}

댓글