1. 삽입 정렬 insertion sort

2750. 수 정렬하기

https://www.acmicpc.net/problem/2750

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1<=N<=1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절대값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 

5
5
2
3
4
1

예제 출력 

1
2
3
4
5

1. 삽입정렬 소개

인간은 정렬을 어떻게 하는가? 누군가에게 숫자 타일을 여러개 주고 오름차순으로 바닥에 정렬하라고 한다면,

아마 다음과 같은 과정으로 정렬할 것이다.

{5, 3, 4, 1, 2}

1) 일단 헷갈리니까 하나를 내려놓는다.

-> {5}

2) 이제 다음 타일을 내려놓아야 하는데, 들고 있는게 내려놓은 타일보다 작다면 앞에 놓고, 아니면 뒤에 놓을 것이다.

즉 적당한 위치에 놓을 것이다.

-> {3, 5}

3) 2의 과정을 반복한다.

-> {3, 4, 5} -> {1, 3, 4, 5} -> {1, 2, 3, 4, 5}

삽입정렬은 우리의 정렬방법과 닮았다.

배열을 앞에서 부터 정렬하는데, 이미 정렬된 부분과 비교하여 현재 보고 있는 요소를 알맞은 부분에 삽입하는 정렬이다.

그러면 알맞은 부분에 삽입은 어떻게 해야할까?

현재 보고있는 부분을 제외하고 앞의 부분은 이미 정렬되어 있음을 기억해야 한다.

따라서 한 칸씩 돌아가는데, 맨 처음으로 돌아가거나 자신보다 작은 원소를 찾으면 그만 돌아가야 한다.

{1, 2, 4, 5} 까지 정렬했고 이제 3을 삽입하려고 할 때, 2를 보고 그만 돌아가는 것이다. -> {1, 2, 3, 4, 5}

돌아가는 중에는 3보다 큰 숫자라면 뒤로 한 칸씩 미뤄줘야 한다. 그래야 3이 들어갈 자리가 생긴다.

따라서 3의 현재 인덱스(4)와 숫자 3을 기억해야 한다. 5가 바로 뒤로 밀려오기 때문이다.

3보다 작은 첫 숫자 2(인덱스 : 1)를 발견했으면 이제 바로 뒷 칸(인덱스 : 2)에 삽입하면 끝이다.

gif로 확인해보자.

오른쪽으로 한 요소씩 진행하면서 계속 정렬하고 정렬하는 과정이 잘 보인다. 

2. 코드

#include <stdio.h>
#include <vector>
using namespace std;
 
int n, tmp;
vector<int> v;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &tmp);
        v.push_back(tmp);
    }
 
    for (int i = 1; i < n; ++i) {
        tmp = v[i];
        int tar = i - 1;
 
        while ((tar >= 0) && (v[tar] > tmp)) {
            v[tar + 1] = v[tar];
            tar--;
        }
        v[tar + 1] = tmp;
    }
 
    for (int i = 0; i < n; ++i)
        printf("%d\n", v[i]);
 
    return 0;
}

3. 시간 복잡도

매번 정렬한다는 부분 알고리즘 때문에 딱 봐도 느린 알고리즘이다. 

결국 내림차순으로 되어있는 수열을 정렬한다면 (최악의 경우)

n + (n - 1) + (n - 2) + ... = n * (n - 1) / 2 번 걸릴 것이다.

따라서 O(n ^ 2) 의 시간복잡도를 가진다.