컴퓨터 알고리즘 초급 #3 ( 삽입정렬 in c )

삽입정렬이란 삽입하여 정렬하는 것이다. 

 

입력 :

n개의 숫자

 

출력 :

n개의 숫자가 점점 커지는 순서로 정렬 , 가장 큰 숫자가 가장 오른쪽으로 간다. ( 오름차순 )

 

 

 

무엇을 삽입할 것인가?

 

Key 값과 정렬된 리스트가 주어졌을 때, Key 값을 정렬된 리스트의 알맞은 위치에 삽입

 

Key가 3이고 정렬된 배열이 <1,2,4,5,6>일 때

 

1과 2 사이에 3을 넣음으로써 

<1,2,3,4,5,6> 으로 정렬함.

 

 

정렬을 시작할 때 처음 값 한개는 미리 넣어둔다.

 

두번째 숫자부터는 Key 값으로 생각을 하고 삽입한다.

 

즉 <3,2,4,5,1,6> 일 때

 

<3>

 

<2,3>

 

<2,3,4>

 

<2,3,4,5>

 

<1,2,3,4,5>

 

<1,2,3,4,5,6> 

 

이렇게 들어간다고 생각하면 된다.

 

과정은

만약 삽입할 key가 가장크면 맨뒤에 남고,

아니면 그 앞자리와 자리를 바꿈. 

 

이걸 앞자리보다 key가 클때까지 반복하면

자기자리에서 멈추게 된다.

 

 

 

 

 

 

 

 

 

 

수행시간을 분석해보면, 

 

몇번 째 자리가 key값이 들어가야 하는지 계속해서 확인해야한다. 

 

그래서 정렬된 , 정렬되고 있는 배열의 숫자와 key값에 따라서 몇번을 확인하게 될지 알기 어렵다.

 

즉 입력의 크기가 동일하더라도

 

최선의 경우와 최악의 경우, 평균의 경우의 수행시간이 다르다.

 

이미 정렬되어 있는 정렬이라면 : n

 

반대로 정렬되어 있는 정렬이라면: O(n^2) 

 

 

/// 다른 삽입, 선택, 버블 등은 n^2이지만 삽입은 상황에 따라 더 빠를 수 있다는 장점이 있다. /// 

 

 

 

 

삽입정렬 코드 in c

 

#include <stdio.h> 

int main(void) { 

	int i, j, temp; 

	int array[10] = {4, 5, 7, 2, 8, 1, 9, 3, 6, 10}; 

		for(i=0; i< 9; i++){ // 9번 반복한다.
			j = i;//
			while(array[j] > array[j+1]){ // array[0]>array[1] 만약 맨 앞자리보다 2번째가 작으면 
				temp = array[j]; 
				array[j] = array[j+1]; // 2번째와 앞자리를 바꿔준다.
				array[j+1] = temp; // 앞자리에는 가장 작은수가 들어가짐.
                j--; // 이걸 뒷자리부터 계속해서 비교해서 자기자리에 찾아 들어간다.
                //들어가게 되면 앞자리보다 뒷자리가 크므로 while 탈출
							}
				} //9번 반복

// 결과 확인 for(i=0 ; i<10; i++){ 

printf("%d ", array[i]); 
								} 
                                
 return 0; 
 }

 

2020/03/10 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #1 ( 컴퓨터 알고리즘 개요 )

2020/03/10 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #2 ( 선택정렬 in c )