[알고리즘] 삽입정렬(Insertion Sort)

작업 환경

- OS : Ubuntu 14.04.5 LTS

삽입정렬이란?

- 정렬 대상을 두 부분으로 나눠서 정렬 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 삽입해 가면서 정렬하는 알고리즘

그림 참조 - 윤성우의 열혈 자료구조

문제

배열에 3,1,5,4,2를 저장하고 삽입정렬을 이용하여 오름차순으로 정렬하시오.

insert_sort.c

#include<stdio.h>

void InsertSort(int *arr , int cnt);

int main()

{

int arr[5] = {3,1,5,4,2};

int i , cnt;

cnt = sizeof(arr) / sizeof(int);

InsertSort(arr , cnt);

for(i=0 ; i<cnt ; ++i)

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

putchar('\n');

return 0;

}

void InsertSort(int *arr , int cnt)

{

int i , j , data;

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

{

data = arr[i];

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

{

if(arr[j] > data)

arr[j+1] = arr[j];

else

break;

}

arr[j+1] = data;

}

}

컴파일 : gcc insert_sort.c -o insert_sort

실행 : ./insert_sort

실행결과