삽입 정렬

삽입 정렬(Insertion Sort)

---

 삽입 정렬은O($n^2$)의 복잡도를 가진 대표적인 알고리즘이다. 

비교 정렬, 제자리 정렬이면서 온라인 정렬 방식으로, 정렬할 원소를 이미 정렬된 배열의 적절한 위치에 삽입한다는 의미이다.

평균적으로 같은 O($n^2$)의 복잡도 정렬 알고리즘 중 좋은 성능을 보여주나, 자료구조에 따라서 최악의 성능이 나온다.

 다른 복잡도의 정렬 알고리즘에 비해 이해하기는 쉬우나 구현하기는 조금 까다로운 알고리즘이다. 하지만 연결리스트라는 자료구조일 경우 정말 효율적인 알고리즘이고, 이미 정렬되어 있는 배열에 원소를 하나씩 삽입/제거하는 경우에 최고의 정렬 알고리즘이라고 평가받는다.

정렬 방법(오름차순)

---

 배열에서 어떤 원소를 자신보다 작은 원소가 나올 때까지 왼쪽으로 이동시키면 된다.

 다른 O($n^2$)복잡도 알고리즘과 반대로 처음엔 총 $1$회 비교-교환하지만 두 번째부터는 앞의 원소를 포함해야 하므로 $2$회 $3$회 $...$ $n-1$회까지 비교하게 되어 총 $\frac{n(n-1)}{2}$회 비교한다. 

▶ 과정을 순서대로 표현하면 다음과 같다.

1. $i=j=1$로 시작하여 주어진 배열의 $j$번 인덱스 값과 $j-1$번 인덱스 값을 비교한다.
2. $j=0$이 되거나 $j-1$인덱스 값이 $j$인덱스 값보다 작을 때까지 $j$값을 $1$씩 빼며 반복 교환한다. 
3. 위 과정이 한 번 끝나면 $i = i +1, j = i$연산을 하고 $i==n$이 될 때까지 반복한다.

글로 표현하면 어려우니 그림과 함께 수행 과정을 살펴보자.

위와 같이 8개의 원소가 임의의 순서로 저장된 배열이 있다.

0번 인덱스는 건너뛰고 1번 인덱스부터 검사한다.

하지만 2번 인덱스까지 봤을 때는 잘 정렬된 배열이기 때문에 교환을 하지 않는다.

 

3번 인덱스의 값 $2$를 볼 때, 3번 인덱스 값보다 비교 인덱스 값이 작거나 비교 인덱스가 0번이 될 때까지 이동하면

3번 인덱스 값 $2$는 끝까지 계속해서 자리를 교환하며 한 칸씩 이동한다.

그 후 4번 인덱스 값 $138$을 기준으로 똑같이 비교-교환을 수행하면

$138$은 자신보다 값이 작은 2번 인덱스 값 $126$을 마주치고 3번 인덱스 위치에 멈추게 된다.

그 후에 나머지 원소를 반복적으로 적절한 위치에 삽입하면

5번 인덱스까지 정렬

6번 인덱스까지 정렬

총 7회 삽입을 수행하게 된다.

이처럼 정렬이 된 것을 확인할 수 있다.

위의 경우는 끝까지 비교-교환을 수행하였지만 간혹 

마지막까지 비교-교환을 수행하지 않더라도 정렬이 되어있는 경우가 있다.

버블 정렬의 경우는 이런 경우 반복을 멈출 수 있지만, 삽입 정렬은 중간에 멈출 수 없기 때문에

모든 경우에 O($n^2$)의 시간 복잡도를 가지게 되므로 비효율적이다.

일반적인 순차 자료구조를 사용하게 되면 삽입할 공간을 만들기 위해 수차례 데이터를 이동시키는 작업이 필요하므로 

필요 이상의 연산, 즉 오버헤드가 발생하지만

연결 자료구조를 사용하게 되면 한 번에 이동시키는 것이 가능하기 때문에 고성능을 발휘한다.

또한 같은 O($n^2$) 복잡도의 알고리즘에서 구현하기 어느정도 까다롭기 때문에 연습용으로 

한 번쯤은 구현해볼 만한 가치가 있는 것이라 생각된다.

소스코드

---

 간단한 알고리즘인 만큼 소스코드 또한 간결한데, C언어를 사용하여 구현한 코드를 게시하여 보겠다.

#include<stdio.h>
#define LEN 8
#define INF 0xFFFFFFF
 
void Swap(int *a, int *b){ // 두 수를 바꾸는 함수
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
void PrintArray(int *arr, int len){ // 배열 값들을 출력하는 함수
    for(int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
void Insertion_Sort(int *arr, int len){ // 삽입정렬
    for(int i = 1; i < len; i++){
        int j = i - 1, data = arr[i]; // 추가할 i번째 데이터 미리 저장
        while(j >= 0 && arr[j] > data){
            arr[j + 1] = arr[j]; // 앞의 데이터를 뒤로 한 칸씩 당겨줌
            j--;
        }
        arr[j + 1] = data;
        PrintArray(arr, len);
    }
}
 
int main(){
    int arr[] = {68, 126, 1001, 2, 138, 338, 168, 58};
    Insertion_Sort(arr, LEN);
    return 0;
}

 이 글은 제가 공부하면서 이해한 부분을 정리한 것입니다.

 틀린 부분이 있다면 댓글로 피드백 해주시고 도움이 되셨다면 추천과 공감 부탁드리겠습니다.

출처 : 나무위키(정렬 알고리즘)