4. 삽입 정렬(Insertion Sort)

#삽입 정렬 알고리즘

a[0]부터 a[i-1]까지 정렬되어 있을 때, a[i]까지 포함하여 정렬하는 알고리즘을 이용

 

insertion sort

 

 

#구현

#include <iostream>
using namespace std;

void insertionsort(int* a, int n);

int main(){
    int n;
    cin>>n;
    int* a= new int[n];
    for(int i=0; i<n; i++)
        cin>>a[i];

    insertionsort(a,n);

    for(int i=0; i<n; i++)
    cout<<a[i]<<" ";

    return 0;
}

void insertionsort(int* a, int n){
    int tmp, j;
    for(int i=1; i<n; i++){
        tmp=a[i];
        for(j=i-1; j>=0; j--){
            if(tmp<a[j]) a[j+1]=a[j];
            else break;
        }
        a[j+1]=tmp;
    }
}

 

 

#시간복잡도 분석

최악의 경우: 역순으로 정렬되어 있는 입력 => n(n-1)/2 => O(n*n)

가장 좋은 경우: 정렬되어 있는 입력 => O(n)

 

삽입정렬은 정렬되어 있는 경우 아무런 변화가 없기 때문에 데이터가 거의 정렬된 상황에서는 매우 빠르다. 

 

 

#정리

	Best	Worst	Average	Stable?	In-Place?
선택정렬	O(n^2)	O(n^2)	O(n^2)	??	Yes
버블정렬	O(n^2) -> O(n)	O(n^2)	O(n^2)	Yes	Yes
삽입정렬	O(n)	O(n^2)	O(n^2)	Yes	Yes