아래 자료는 한국방송통신대학교 인천지역 컴퓨터과학과
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. 정의 : 삽입의 경우 입력순서에 따라 시간 복잡도가 달라지며,자기 자리를 찿기 위해
한번에 한자리씩 이동하기 때문에 시간이 많이 걸린다는 단점이 있다.
이와 같이 단점을 보안하기 위해 셸 정렬이 있다
*/
'기타' 카테고리의 다른 글
윈도우8 갑자기 느려질때 대처법 (0) | 2014.02.04 |
---|---|
C언어로 구현한 선택정렬 (0) | 2013.10.24 |
C언어로 구현한 버블정렬 (0) | 2013.10.24 |
C언어로 구현한 단순연결리스트 (0) | 2013.10.21 |
C언어로 구현한 원형 큐 소스코드 (0) | 2013.10.08 |