삽입 정렬 (중요)

삽입정렬

삽입정렬이란?

삽입정렬은 크기가 n인 집합일 때,
2개, 3개, 4개 ... n-1개씩 비교대상이 늘어나는 것이 특징이다.

단, 사이클마다 대상 집합이 이미 정렬되어 있는 경우에는 비교가 일어나지 않는다. 그래서 무조건(정렬이 되어 있든 아니든) 비교하는 버블정렬보다 평균적으로는 성능이 좋다.

아래에서 예시로 정렬할 때 오름차순을 목표로 한다.

특징

1.정렬 대상이 처음에는 2개.
사이클을 반복할 때마다 1개씩 커집니다. 최대 n-1까지 커진다.

2.정렬 대상의 가장 오른쪽 요소가 대상 중에서 가장 큰 값인지 확인한다.
그렇지 않다면 그 것의 적절한 위치를 찾아준다. 자신보다 큰 요소를 만날 때 까지 탐색한다.

3.적절한 곳을 찾았다면, 자신보다 큰 요소들을 모두 한칸씩 앞으로 이동시킨다. 그리고 새로 생긴 곳에 위치시킨다.

예시

5 1 6 4 2 3

데이터 집합 크기는 6이다.

일단 비교 대상은 2개다. 5와 1.

가장 오른쪽 요소인 1이 가장 큰값을 가지는지 확인해본다.

1을 뽑는다. 1보다 큰 수 5 앞에 놓아야 한다.

5를 이동시켜서 오른쪽으로 밀어서 공간을 만든다.

빈 곳에 1을 삽입한다.

결과 : 1 5 6 4 2 3

비교 대상은 3개다. 1, 5, 6

가장 오른쪽 요소 6이 가장 큰 값을 가지는지 확인한다. (6을 그 앞의 숫자 5와 비교한다.)

6이 더 크다.

그 앞의 요소들은 이미 정렬을 거친 숫자들이니까 확인할 필요가 없다. (!!)

다음 단계로 넘어간다.

비교 대상은 4개다. 1, 5, 6, 4

가장 오른쪽 요소 4가 가장 큰 값을 가지는지 확인한다. (4를 그 앞의 수 6과 비교한다.)

4가 작으니까 이동이 필요하다.

4를 뽑는다.

6, 5, 1 순으로 탐색해보니까 1 앞에 오면 된다.

5와 6을 오른쪽으로 민다. 빈 공간에 4를 삽입한다.

결과 : 1 4 5 6 2 3

삽입정렬 코딩해보기 1

#include <stdio.h>
#include <string.h>

void InsertionSort(int dataset[], int length){
    int i=0, j=0, target=0;

    for(i=1; i<length; i++){

        if(dataset[i-1] < dataset[i]){
            continue; // 맨 오른쪽 요소가 가장 크다면 정렬이 필요 없다. 
        }

        target = dataset[i]; // 맨 오른쪽 요소의 적절한 위치 탐색시작

        for(j=0; j<i; j++){

            if(dataset[j] > target){
                // 데이터를 쭈욱 민다. 
                memmove(&dataset[j+1], &dataset[j], sizeof(dataset[0])*(i-j));
                dataset[j] = target;
                break;
            }
        }
    }
}

int main(void){

    int dataset[] = {5, 3, 6, 4, 1, 2};
    int length = sizeof(dataset) / sizeof(int);
    int i = 0;

    InsertionSort(dataset, length);

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

    return 0;
}

memmove() 함수

메모리에 내용을 이동시키는 함수이다. C표준함수.

배열처럼 연속된 데이터를 이동시킬 때 유용하다.

반복문으로 이 함수의 기능을 구현할 수 있지만 성능이 떨어진다.

void* memmove(void* dest, const void *src, size_tn)

dest: 복사의 대상이 되는 목적지 주소

src: 복사할 원본이 있는 주소

size_tn : 복사할 메모리 길이 (byte)

memmove() 함수는 데이터를 '이동'시키고 memcpy() 함수는 데이터를 '복사'한다.

삽입정렬 코딩해보기 2

memmove() 메모리 복사 없이, 배열의 데이터 복사하는 방식으로 정렬해본다.

i와 j로 만든 이중 for문인데,

i는 1부터 시작한다. 비교 집합의 맨 오른쪽 수가 i인데 temp 변수에 기억해둔다.

j 반복문 안에서, temp 보다 큰 수가 있다면 하나씩 오른쪽으로 당긴다.

적절한 위치를 발견하는 순간 temp에 저장된 값을 삽입한다.

input.txt 입력 설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다.
6
11 7 5 6 10 9

출력 설명
오름차순으로 정렬된 수열을 출력합니다.
5 6 7 9 10 11

#include <stdio.h> 

int main(int argc, char** argv){

    int a[100], num=0, temp=0, i=0, j=0;

    freopen("input.txt", "rt", stdin);

    scanf("%d", &num); // 데이터 개수  

    for(i=0; i<num; i++){ // 데이터 저장  
        scanf("%d", &a[i]);
    }

    for(i=1; i<num; i++){ // 오름차순으로 정렬 

        temp = a[i]; // a[i]의 적당한 위치를 탐색 시작  

        for(j=i-1; j >= 0; j--){ // 오른쪽에서 왼쪽으로 순회  

            if(a[j] > temp){  
                a[j+1] = a[j];
            }else{
                break;
            }
        }

        a[j+1] = temp; // 적당한 위치에 삽입. 
    }

    for(i=0; i<num; i++){ // 정렬 결과  
        printf("%d ", a[i]);
    }

    return 0;
}

• 헷갈렸던 부분 정리!

데이터집합이 3 2 4 5 라고 가정한다.

i는 인덱스 1부터 temp 에는 2 가 들어가 있다.
j는 인덱스 i-1부터 시작하니까 0 이 들어가 있다.

for문의 조건을 확인한다.
j는 0보다 크거나 같으니까, 반복문 안의 코드가 실행된다.
3이 2보다 크니까 if문 조건을 만족한다.
그래서 인덱스 1 자리에 인덱스 0의 값이 복사된다.
그 결과 3 3 4 5 가 된다.
반복문 안의 코드 수행이 끝났으니까, j--가 수행된다.
j는 -1이 된다.
다시 for문의 조건을 확인한다. j>=0 을 만족하지 못하니까 반복문을 종료한다.

j는 -1인 채로 남아 있었으니까, arr[j+1] 은 arr[0]을 의미한다.
그래서 인덱스 0 자리에 temp값 2를 넣는다.
그 결과 2 3 4 5 가 된다.