C++ 삽입 정렬 - 정렬3

삽입 정렬은 O(n²) 정렬 알고리즘 중 가장 효율적인 알고리즘이다

삽입 정렬은 한 원소를 선택하여 그 원소를 알맞은 위치에 삽입하는 알고리즘이다

 

아이디어는

1. 한 원소를 선택하여

2. 선택한 원소보다 작은 원소를 만날때까지 앞의 원소와 비교한다

3. 앞의 원소가 선택한 원소보다 작다면 선택한 원소와 자리를 바꾼다

4. 선택한 원소보다 작은 원소를 만나면 멈춘다

 

언뜻 보면 버블 정렬과 유사해 보이지만 다른 점은 정렬을 멈추는 지점을 알기 때문에 

선택 정렬이나 버블 정렬과 다르게 불필요한 정렬을 하지 않는다

선택 정렬에서는 왼쪽의 원소들은 이미 정렬이 되어있다는 가정을 하기 때문에

왼쪽으로 탐색했을 때 자기 자신보다 작은 원소가 있다면 거기서 멈추면 된다

int* InsersionSort(int* arr, int size){

    for(int i=0; i<size-1; i++){	//size-1을 해주는 이유는 맨 앞의 원소는 갈곳이 없기때문에 
        int j = i;			//그 다음 원소부터 정렬하기 때문이다
        while(arr[j] > arr[j+1]){
            int temp = arr[j+1];	//j+1이 선택한 원소라고 생각하면 편하다
            arr[j+1] = arr[j];
            arr[j] = temp;
            
            j--;
            if(j < 0){
                break;
            }
        }
    }

    return arr;
}

그런 특징이 효율, 시간 복잡도에 영향을 주는데,

 

삽입 정렬의 시간 복잡도는 

최악의 경우 O(n²)이지만

이미 정렬이 완료된 경우 O(n)의 시간 복잡도를 가지며

어느 정도 정렬이 되어있는 경우 O(n²) 보다 적은 시간 복잡도를 가진다