C++/ 삽입정렬 이번에야 말로 제대로 이해하기

알고리즘 공부하면서 정렬을 수 없이 많이 거쳐갔지만.. 실제로 머리에 남은건 1도 없다

이번에야 말로 제대로 이해하고 넘어가야 다음 것들도 수월하게 할 수 있을 것이라는 생각이 들어서 정리해 보려고 한다.

 

삽입정렬(Insertion sort)이란?

 

- 자료 배열의 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 정렬.

 

알고리즘 순서

1. 첫 번째 자료를 tmp 변수에 선정. 

2. i=1, 즉 두 번째 자료에서부터 for loop를 돌린다. 

3. 이중 for loop 안에서는 j가 i-1부터 0까지 돌며 , tmp와 각 자리의 값을 비교한다.

4. 만약 tmp 값이 j 자리의 자료보다 작다면, j 자리의 자료를 오른쪽으로 한 자리 당긴다. (내림차순 기준)

5. j+1 자리에는 tmp 값을 할당한다.

 

삽입정렬

 

C++ 코드

#include <stdio.h>

using namespace std;

int main(){
    int a[100],n,i,j,tmp;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a);
    }

    while(j>=0 && a[j]>tmp){
	    a[j+1]=a[j];
	    j--;
    }
    a[j+1]=tmp;

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

중간 while 문은 while로도 구현할 수 있다는 의미에서 추가,,

 

for 문 위주로 보면 내부 for문에서 왼쪽으로 가면서 비교 후에 한 자리식 당기는 것이 포인트임.

물론 i 값이 변하면 tmp도 새로 할당됨.

 

"이미 정렬된 데이터 사이에서 자리를 찾아 삽입하는 것"

이 핵심인 것이다..

 

관련 문제를 풀면서 삽입정렬의 특성은 전혀 고려하지 않고 멋데로 코드를 짜버린 후 현타가 씨게 왔다,,

 

 

 

예시문제

 

inflearn 강의 38번 문제.

문제 내용은 1~N 사이의 원소의 inversion sequence가 주어졌을 때, 원래 배열을 찾는 문제였다.

 

 여기서 Inversion sequence란?

- 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열에서 1~n의 각각의 수 앞에 놓여있는 자신보다 큰 수들의 개수를 수열로 표현한 것.

 

My code

#include <stdio.h>
#include <vector>
#include <algorithm>

int main(){
    int n,i,j,idx,tmp,cnt;
    int a[100];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",a[i]);
    }

    for(i=1;i<=n;i++){
        tmp=i;
        cnt=0;
        idx=a[i];
        for(j=idx;j>=0;j--){
            if(a[j]<tmp) cnt++; 
        }
        for(j=(idx+cnt);j<n;j++){
            if(a[j]<tmp) cnt++;
        }
        a[idx+cnt]=tmp;
    }

    for(i=0;i<n;i++){
        printf("%d",a[i]);
    }

    return 0;
}

나는 삽입정렬을 이용하지 않았다.

이게 무슨 알고리즘인지는 묻지 마라. 기원이 없다.

문제를 풀면서 한 생각의 흐름을 말해보자면

 

1. 1부터 자기 자리를 찾는 것으로 함.

2. 1의 idx가 주어 졌을 때, 그 인덱스 왼쪽 기준으로 tmp 값 (지금은 1)과 자리 값을 비교함.

3. tmp보다 작은 자료가 나온다면 cnt를 ++

4. 이후 idx+cnt 부터 배열의 끝까지 다시 tmp 값과 비교함.

5. 최종적으로 tmp 값은 a의 idx+cnt 자리에 배치됨.

 

c++ 컴파일 및 빌드가 되지 않으므로~~~ 결과 확인은 못했다 (조만간 해결해야한다 이것도,,,)

 

어찌됐든 그리 현명한 코드는 아닌 것 같고, for loop 남발하면서 비교하는 코드였다..

선생님께서 올린 코드를 보니 idx와 cnt라는 변수가 조금 비효율적인 것 같은 느낌이 들었다. 

 

 

Teacher's Code

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n,i,j,pos;
    scanf("%d",&n);
    vector<int> is(n+1), os(n+1);
    for(i=1;i<=n;i++){
        scanf("%d",&is[i]);
    }
    for(i=n;i>=1;i--){
        pos=i;
        for(j=1;j<=is[i];j++){ //자리수 "만큼" 자기보다 큰 숫자를 땡기는거임
            os[pos]=os[pos+1]; //만약 5이고 값이 2이면 두 번 앞으로 땡겨서 자리를 찾는 방식.
            pos++;
        }
        os[pos]=i;
    }
    for(i=1;i<=n;i++){
        printf("%d",os[i]);
    }
}

 

 

여기서 is라는 배열은 inversion, os라는 배열은 순행 배열을 뜻한다.

삽입 정렬이 빛을 발하게 하는 아이디어는 배열의 마지막 원소인 n 부터 자리를 찾는다는 것으로 시작한다.

 

pos라는 변수에 i, 즉 자리를 찾아야 하는 그 장본인 값을 넣은 후

이중 루프에서는 j가 is[i], 즉 inversion에서의 값 (i 앞에 있는 i보다 큰 수의 개수) 만큼 os 배열을 왼쪽으로 당긴다

 

내가 위에서 짠 코드에서는 i,j를 단순히 배열의 실제 인덱스나 값에 연관시키려고 한게 다였다

여기서는 j는 자리 옮김 횟수의 용도로 쓰여졌다

 

손으로 8부터 1까지 직접 확인해보아서 이해가 가기는 하지만..

실전에서 저런 코드가 바로 나온다는 것이 나로써 가능할지가 의문이다..^^

기본적으로 숫자들 사이 관계에 대한 센스가 부족한 것 같다 ㅠㅠ