삽입정렬

여전히 느리다

 

삽입정렬이란

삽입정렬은 2번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘입니다. 

 

최선의 경우: 이미 정렬이 완료되어있는 배열, 이 경우에는 삽입할 위치를 지정할 필요없이 O(N)으로 끝이 납니다. 

Worst Case: 내림차순으로 정렬이 된 배열, 이 경우에는 삽입할 위치를 찾기 위해 탐색하기 때문에, 시간복잡도는 O(N^2)입니다.

 

예제

8,5,6,2,4를 오름차순으로 정렬해 봅시다.

 

코드 예시

void insertion_sort(vector<int> &arr) {
    int n = arr.size();
    int i = 0, j = 0;
    for (i = 1; i < n; i++) {
        int key = arr[i]; // 이번 루프때 삽입해야할 값 지정
        for (j = i - 1; j >= 0 && key > arr[j]; j--) {
            arr[j + 1] = arr[j]; // 배열의 시작위치 혹은 삽입해야할 위치에 도달할때까지 이동
        }
        arr[j + 1] = key; // 삽입
    }

}