cpp) 삽입 정렬, insertion sort

https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

 

 

 

- 삽입정렬

 

배열의 각 요소를, 앞에서부터 하나씩 자신의 자리를 찾아 삽입

 

 

- 절차(오름차 기준)

 

i) 배열의 1번 요소를 0번째 원소와 비교. 더 작다면 0번째 요소를 뒤로 옮기고, 그 앞에 1번 요소를 삽입

ii) 배열의 2번 요소를, 1번부터 0번 원소를 비교해 자리 설정

iii) 배열의 n번 요소를, n-1번부터 0번 원소와 비교해 자리 설정

 

 

- 시간복잡도

 

최악의 경우 = 모든 원소가 역순으로 정렬되어 있는 경우

외부 루프를 N-1번 도는 동안 비교연산은 1, 2, ... , (N-1)번 수행된다. 

T(n) = 1+2+...+(N-1) = (N-1)*N/2

O(n) = n^2 

 

 

- 특징

 

정렬에 사용하는 외부 메모리 X 

이를 In-place sort라고 한다.

 

#include <iostream>
using namespace std;

void insertion(int *arr,int len) {
    int i,j,flag;

    for(i = 1; i < len; i++){
        flag = arr[i]; // 현재 대상 요소

        for(j = i-1; j >= 0; j--){
            if(flag < arr[j]){
                arr[j+1] = arr[j];
            } else {
                break;
            }
        }
        arr[j+1] = flag;
    }

    for(i = 0; i < len; i++){
        cout << arr[i] << endl;
    }
}

int main() {
	// 길이 n 입력
    int n;
    cin >> n;

    int *arr = (int *)malloc(sizeof(int) * n);
    
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }


    insertion(arr,n);

    free(arr);

    return 0;
}

백준 2750번 참고 2750번: 수 정렬하기 (acmicpc.net)