[정렬] Insertion Sort

삽입 정렬은 원소의 앞에 위치한 값들과 비교해 자신의 위치를 찾아 그 위치에 삽입하는 정렬 방법이다.

다음을 예로 들어 보자.

3

1

2

5

4

2번째에 위치한 1의 위치를 찾는다.

앞에 위치한 3이 더 크므로 3을 한 칸 뒤로 밀고, 그 앞에 숫자가 더 없으므로 1을 그 위치에 저장한다.

1

3

2

5

4

3번째에 위치한 2의 위치를 찾는다.

앞에 위치한 3이 더 크므로 3을 한 칸 뒤로 밀고, 1은 2보다 작으므로 2를 그 자리에 저장한다.

1

2

3

5

4

4번째에 위치한 5의 위치를 찾는다.

앞에 위치한 3이 5보다 작으므로 그대로 둔다.

5번째에 위치한 4의 위치를 찾는다.

앞에 위치한 5가 더 크므로 5를 한 칸 뒤로 밀고, 그 앞의 3은 4보다 작으므로 4를 그 자리에 저장한다.

1

2

3

4

5

매번 앞에 위치한 값들과 비교해 자기 자신의 위치를 찾아야하고, 이 과정을 2번째~n번째까지 n-1번 거치므로 O(n^2)의 시간이 걸린다.

---

#include <iostream>

using namespace std;

int main(void){
    int n = 10;
    int arr[10] = {2, 1, 9, 3, 4, 7, 2, 8, 10, 5};

    for(int i = 1; i < 10; i++){
        // 앞으로 가며 자신의 위치 찾기
        int cur = arr[i];
        int loc = i;
        for(int j = i-1; j >= 0; j--){
            if(arr[j] <= cur){
                break;
            }
            arr[j+1] = arr[j];
            loc = j;
        }
        arr[loc] = cur;
    }

    for(int i = 0; i < 10; i++){
        cout << arr[i] << " ";
    }
    cout << "\n";

    return 0;
}