[알고리즘 구현] InsertSort

InsertSort

• O(n^2)의 알고리즘
• 앞의 값과 비교하여 오름차순이 아닌경우, 바꾼다.
• 오름차순을 찾는 부분까지 계속 바꿔간다.

코드(C++)

void insertSort(int *arr){
    for(int i=1;i<n;i++){
        int cur = i;
        for(int j=1;j<=i;j++){
            if(arr[i-j] > arr[cur]){
                swap(arr[i-j], arr[cur]);
                cur--;
            }
        }
    }
}