[백준(BOJ)] 2750번 C++ 풀이

자료구조를 놓은 지 너무 오래되어서 가장 기본인 정렬 문제도 정리할 겸 이 문제를 풀었다.

 

문제에 대한 설명에서 시간 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있고, 그 예로 삽입 정렬, 거품 정렬 등이 있다고 한다. 

 

그래서 그냥 삽입 정렬로 풀어보기로 했다.(거품 정렬은 다음 포스팅에서 해보도록 하겠다) 그럼 우선 삽입 정렬에 대해 정리해보자.

 

 

삽입 정렬(insertion sort)

삽입 정렬이란 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입해 정렬을 완성하는 알고리즘이다.

 

구체적인 과정을 살펴보겠다. 

삽입 정렬은 2번째 자료부터 시작하여 그 요소의 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬한다.

즉, 2번째 자료는 1번째 자료, 3번째 자료는 2, 1번째 자료, 4번째 자료는 3, 2, 1번째 자료와 비교한 후 해당 자료를 삽입할 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 해당 위치에 자료를 삽입하기 위해 다른 자료들을 한칸 씩 뒤로 이동시킨다.

 

 

 

그림을 살펴보면 해당 배열은 9, 7, 6, 15, 17, 5, 10, 11 순이고 이를 오름차순으로 정렬하려한다. 삽입하려는 요소를 Key라고 부르겠다.

삽입 정렬은 2번째 자료와 시작한다고 하였으니 Key는 7이다. Key의 왼쪽을 보면 9는 7보다 크기때문에(9>7) 7은 9의 앞쪽에 있어야 한다. 따라서 9를 2번째로 이동시키고 1번째 자리에 7을 삽입한다. 

이번에는 3번째 자료를 Key로 설정하고(Key=6) 왼쪽의 2번째 요소를 살펴보면 9는 6보다 크기때문에(9>6) 6은 9의 앞쪽에 있어야 한다. 따라서 9를 3번째로 이동시킨다. 그리고 1번째 요소를 살펴보면 7은 6보다 크기때문에(7>6) 6은 7의 앞쪽에 있어야 한다. 결국 7을 2번째로 이동시키고 Key(6) 값이 1번째 자리에 삽입된다.

다음으로 4번째 자료를 Key로 설정하면(Key=15) 바로 왼쪽의 3번째 요소와 비교했을 때 9는 15보다 작다.(9<15) 여기서 Key의 왼쪽은 이미 정렬이 완료되었기 때문에 더이상 그 앞의 요소들과 비교할 필요없이 Key를 5번째 자료로 설정한다. 

이런 과정을 반복해 결국 Key가 마지막 요소일 때의 비교와 삽입을 다 마치면 삽입 정렬이 완료된다.

 

 

코드

#include <iostream>
using namespace std;

void insertion_sort(int list[], int n){
    int i, j, key;
    
    for(i=1; i<n; i++){
        key=list[i];	//key값이 되는 배열의 i번째 요소(삽입할 것)
        for(j=i-1; j>=0 && list[j]>key; j--){	//key와 차례로 비교되는 (i-1)~1번째 요소(j로 지칭)
            list[j+1]=list[j];	//비교값이 key보다 클 경우 해당 값을 한칸씩 뒤로 이동
        }
        list[j+1]=key;	//적절한 위치에 key값 삽입
    }
}

int main(){
    int i, j, n;
    cin >> n;
    
    if(n>1000 || n<=0){
        cout << "input error" << endl;
        return 0;
    }
    
    int a[n];
    for(i=0; i<n; i++){
        cin >> a[i];
    }
    
    insertion_sort(a, n);
    
    for(j=0; j<n; j++){
        cout << a[j] << endl;
    }
    return 0;
}

 

 

삽입 정렬의 시간복잡도

Best case : 이미 정렬이 완료되었기 때문에 이동없이 비교만 이루어지는 경우

  -> 비교하는 외부 루프 동작 : (n-1)번  //각 루프 별로 Key와 바로 왼쪽 요소만 비교

  -> Best T(n) = O(n)

 

Worst case : 입력자료가 내림차순으로 되어있을 때 오름차순으로 만들어야 하는 경우

  -> 비교하는 외부 루프 동작 : 1+2+...+(n-2)+(n-1)= n(n-1)/2 = O(n^2)

  //각 루프 별로 Key와 왼쪽 요소들을 전부 비교

  -> 교환하는 내부 루프 동작 : 1+2+...+(n-2)+(n-1)= n(n-1)/2 = O(n^2)

  //외부 루프의 각 단계마다 (i-1)번의 이동 발생

  -> Worst T(n) = O(n^2)

 

다음에는 거품 정렬로 이 문제를 풀어보겠다.