삽입 정렬(insertion sort) 구현하기(c++)

삽입정렬은 idx기준으로 더 이전의 idx값들과 비교하면서, 기준값들보다 더 큰 값이 있다면 자리를 바꿔주는 형태로 진행된다.

삽입정렬은 최선의 경우에 n번만 비교를 하게 되므로 ex) 1, 2, 3, 4 ,5 -> O(n)의 시간복잡도를 가진다.

O(n^2)의 시간복잡도를 가지는 sorting algorithm 중에서는 가장 빠르다.

 

 

*시간복잡도*

Best	Avg	Worst
O(n)	O(n^2)	O(n^2)

 

코드 첨부

// 삽입 정렬 구현(오름차순)
#include <iostream>
using namespace std;
 
int arr[5] = {8, 5, 6, 2, 4};
 
void insertion_sort(int arr[], int size)
{
    for(int i=1; i<size; i++){
        int cmp = arr[i];
        for(int j=i-1; j>=0; j--){
            if(cmp<arr[j]){ // 뒤로 밀기
                arr[j+1] = arr[j];
                arr[j] = cmp;
            }else{
                break;
            }
        }
    }
}
 
int main()
{
    insertion_sort(arr, 5);
    for(int i=0; i<5; i++){
        cout<<arr[i]<<" ";
    }
    cout<<"\n";
}

 

 

위의 표는 아래 블로그에서 참조했습니다.

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog