C언어로 구현한 삽입정렬

아래 자료는 한국방송통신대학교 인천지역 컴퓨터과학과

2학년 과대표님꼐서 작성하신 소스코드를 수정한 것입니다.

출처 : http://cafe.daum.net/ICCS/LcpH/22

- 위 사이트는 가입/등업이 필요합니다.

※ for문 내에서 변수선언이 가능하도록 하기 위해 C++로 작성되었습니다. 따라서 파일의 확장자를 *.cpp로 저장하셔야 정상적인 결과를 확인하실 수 있습니다.

----------------------------------------------------------------------------------------------

#include<stdio.h>

#include<Windows.h>

/*

삽입정렬 함수

- int[] arr : 정렬시키고자 하는 대상 배열

- int length : 배열의 길이

*/

void Insertion_Sort(int arr[], int length)

{

int before_index = 0;

int next = 0;

/*

삽입정렬은 아래와 같다.

만약 [4]-[2]-[3]-[1] 이라는 배열이 있다고 가정한다.

** for문에서 1회(i=0) 반복시 **

[4]-[4]-[3]-[1]     while문에서 첫 번째 원소와 두 번째 원소를 비교 (i번째 원소값을 i+1번째 원소값에 대입)

[2]-[4]-[3]-[1]     while문이 끝난 후 0번째(before_index) 원소에 1번째(i) 원소에 있었던 값을 삽입

** for문에서 2회(i=1) 반복시 **

[2]-[4]-[4]-[1]     while문에서 두 번째 원소와 세 번째 원소를 비교 (i번째 원소값을 i+1번째 원소값에 대입)

[2]-[4]-[4]-[1]     while문에서 첫 번째 원소와 두 번째 원소를 비교 (while문의 조건식이 참이 되지 않으므로 변화없음)

[2]-[3]-[4]-[1]     while문이 끝난 후 1번째(before_index) 원소에 2번째(i) 원소에 있었던 값을 삽입

** for문에서 3회(i=2) 반복시 **

[2]-[3]-[4]-[4]     while문에서 세 번째 원소와 네 번째 원소를 비교 (i번째 원소값을 i+1번째 원소값에 대입)

[2]-[3]-[3]-[4]     while문에서 두 번째 원소와 세 번째 원소를 비교 (i-1번째 원소값을 i번째 원소값에 대입)

[2]-[2]-[3]-[4]     while문에서 첫 번째 원소와 두 번째 원소를 비교 (i-2번째 원소값을 i-1번째 원소값에 대입)

[1]-[2]-[3]-[4]     while문이 끝난 후 0번째(before_index) 원소에 3번째(i) 원소에 있었던 값을 삽입

결과적으로,

- 위와 같이 배열의 앞에서부터 뒤쪽 방향으로 검색

- 삽입된 위치의 뒤쪽에 있는 모든 원소값들을 한 칸씩 뒤로 이동

- 해당 원소값이 원래 있어야 할 위치값을 찾아서 그 자리에 바로 이동(삽입)하는 알고리즘

*/

for(int i=0; i<length-1 ;i++)

{

//i번째를 포함한 이전 원소의 인덱스 번호를 저장하기 위해

//초기에는 before_index에 i값을 저장

before_index = i;

//i+1번째 원소의 값을 저장

next = arr[i+1];

//i번째 원소부터 0번째 원소까지 역순으로, 순차적으로 검색 (i번째 원소값 보다 더 작은 값이 있는지 검색)

while(before_index>=0 && arr[before_index]>next)

{

arr[before_index+1] = arr[before_index];

--before_index;

}

arr[before_index+1] = next;

}//for()-----

}//Insertion_Sort()=====

/* 알고리즘 교재 소스 임.

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

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

list[j]=list[j-1]

}

}

*/

void main()

{

//배열선언

int arr[]={30, 20, 40, 35, 5, 10, 45, 50, 25, 15};

//배열의 크기

int length = sizeof(arr) / sizeof(*arr);

Insertion_Sort(arr, length);  //함수 호출

for(int i=0; i<length ; i++)

printf("%d ",arr[i]);

//system("pause");

return ;

}

/* 삽입정렬 특징

1. 안정적이다.

2. 제자리 정렬이다.

3. 시간복잡도 최선의 경우 O(n) 1, 2, 3, 4, 5 입력시...

4. 시간복잡도 최악의 경우 O(n2) 5, 4, 3, 2, 1 입력시...

5. 정의 : 삽입의 경우 입력순서에 따라 시간 복잡도가 달라지며,자기 자리를 찿기 위해 

한번에 한자리씩 이동하기 때문에 시간이 많이 걸린다는 단점이 있다. 

이와 같이 단점을 보안하기 위해 셸 정렬이 있다

*/