삽입정렬(Insertion sort) 알고리즘 - c언어 예제

삽입정렬(Insertion sort)

 

이 알고리즘은 다른 알고리즘과 달리 스왑을 하는것이 아니라 temp에 n번째 값을 저장시켜 n-1번째 값이랑 temp를 비교시켜 n-1번째 값이 더 크다면 n번째에 n-1번째 값을 집어넣는 것이다.

n-1 값이 더 크다면 n번째 자리에 temp의 값을 집어 넣는다.

삽입정렬의 시간복잡도는 O(n²)이다.

 

 

 

예제소스

 

#include <stdio.h>
 
#define n 5
 
int main()
{
    int temp;
    int arr[n] = { 65,17,22,1,65 };
    int i, j;
 
    for (i = 1; i < n; i++) {
 
        temp = arr[i];
 
        //중간 과정을 출력
        printf("\n\n%d회전 결과 : ", i-1);
        for (j = 0; j < n; j++) {
            printf("%d ", arr[j]);
        }
 
        //정렬
        for (j = i; j > 0 && arr[j - 1] > temp; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
        
    }
 
    printf("\n\n[정렬 완료]%d회전 결과 : ",n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
 
    return 0;
}