자료구조 :: 삽입정렬 Insertion sort (c/c++ 구현)

삽입 정렬 (Insertion sort)

숫자를 알맞은 위치에 삽입하자

 

삽입정렬은 앞의 원소보단 크고, 뒤에 원소보단 작은 위치에 삽입하는 방법이다.

즉, 앞쪽에 있는 원소들은 이미 정렬이 됐다고 가정한다.

 

#include <stdio.h>
 
int main(void) {
    int i, j, temp;
    int array[10] = {4, 5, 2, 7, 9, 1, 8, 3, 6, 10};
    for(i=0; i< 9; i++){
        j = i;
        while(array[j] > array[j+1]){
            temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
            j--;
        }
    }
    
    // 결과 확인
    for(i=0 ; i<10; i++){
        printf("%d ", array[i]);
    } 
    return 0;
}​

 

 

선택정렬, 버블정렬, 삽입정렬 모두 시간복잡도는 O(N^2)으로 같지만,

특정한 경우(거의다 정렬이 된 상태)에서는 삽입정렬이 매우 빠르다는 장점이 있다.

 

삽입정렬의 시간복잡도는 O(N^2)

 

관련 글

2018/04/29 - [Algorithm/백준 온라인 저지] - 백준/2750번 :: 수 정렬하기

2018/06/16 - [Algorithm/백준 온라인 저지] - 백준/2750번 :: 수 정렬하기 (Java 코드, 삽입 정렬 insertion sort)

2018/04/28 - [Algorithm] - 자료구조 :: 선택정렬 Selection sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 버블정렬 Bubble sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현)

2018/04/29 - [Algorithm] - 자료구조 :: 병합정렬 Merge sort (c/c++ 구현)