삽입정렬(Insertion Sort)

삽입정렬은 최소값을 데이터 리스트의 앞으로 보내는 방법으로 정렬시키는 방법입니다. 순서를 유지하는 안정성있는 정렬방법입니다.

비교횟수는 N(N-1)/2 값을 가지며 수행시간 복잡도는 O(N^2) 값을 가집니다.

삽입정렬 알고리즘

void insert_sort(int arr[], int n)  // 삽입정렬함수
{
    int i,j,t;

    for(i=1; i<n; i++){
        t=arr[i];
        j=i;

        while(arr[j-1] > t && j>0) {
            arr[j]=arr[j-1];
            j--;
        }

        arr[j]=t;
    }
}