자료구조(정렬 알고리즘) - 삽입 정렬(Insertion Sort) C언어 소스 코드

안녕하세요, 츄르 사려고 코딩하는 집사 코집사입니다.

지금까지, 버블 정렬, 칵테일 정렬, 선택 정렬까지 정렬 알고리즘을 다뤘습니다.

이번 글에서는 삽입 정렬입니다.

삽입 정렬(Insertion Sort)이란?

배열에서 key를 설정해주고, key 보다 크면 오른쪽으로 넘겨주면서 적절한 위치에 삽입을 하는 정렬 알고리즘입니다. 

삽입 정렬의 알고리즘

위에서 말했다시피, 크기가 5인 배열 A를 가지고 있다고 가정을 하면, key값을 설정하여 비교를 해가면서 key 값 보다 크면 한 칸씩 뒤로 밀어내고, 적절한 위치에 key값을 넣는 방식입니다. 

삽입 정렬의 시간 복잡도

삽입 정렬은 버블 정렬과 칵테일 정렬, 선택 정렬과 같이 O(n^2)이다.

삽입 정렬 C언어 소스 코드

#include<stdio.h>

int A[10000];

int InsertionSort(int A[],int n);

int main()

{

int number;

printf("배열 크기 입력:");

scanf("%d",&number);

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

{

printf("%d번째 값 입력",i);

scanf("%d",&A[i]);

}

/*for(int i=0;i<number;i++)

{

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

}

*/

InsertionSort(A,number);

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

{

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

}

}

int InsertionSort(int A[],int n)

{

int key;

int i,j;

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

{

key = A[i];

for(j=i-1;j>=0;j--)

{

if(A[j]>key)

{

A[j+1] = A[j];

}

}

A[j+1] = key;

}

}