[알고리즘] 삽입정렬(insertion sort)이란? 삽입정렬 C언어 구현

삽입 정렬(Insertion Sort)

삽입정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

위와 같은 배열을 오름차순으로 정렬한다고 하자.

두 번째 원소인 5부터 시작하여 그 앞의 원소들과 비교를 시작한다.

5와 7을 비교해 5가 더 작으므로 7을 한 칸 뒤로 옮기고 그자리에 5를 삽입한다.

세 번째 원소인 1과 그 앞의 원소 7을 비교해 1이 더 작으므로 7을 한 칸 뒤로 민다.

그 앞의 원소 5와 1을 비교해 1이 더작으므로 5를 한 칸 뒤로 밀고 1을 그 자리에 삽입한다.

네 번째 원소인 4와 그 앞의 원소 7을 비교해 4가 더 작으므로 7을 한 칸 뒤로 민다.

그 앞의 원소 5와 4를 비교해 4가 더 작으므로 5를 한 칸 뒤로 민다.

그 앞의 원소 1과 4를 비교해 4가 더 크므로 1 뒤에 4를 삽입한다.

다섯 번째 원소인 3과 그 앞의 원소 7을 비교해 3이 더 작으므로 7을 한 칸 뒤로 민다.

그 앞의 원소 5와 3을 비교해 3이 더 작으므로 5를 한 칸 뒤로 민다.

그 앞의 원소 4와 3을 비교해 3이 더 작으므로 4를 한 칸 뒤로 민다.

그 앞의 원소 1과 3을 비교해 3이 더 크므로 1뒤에 3을 삽입한다.

배열이 오름차순으로 정렬되었다.

삽입정렬의 특징

• 배열 내에서 교환하는 방식이므로 공간복잡도는 O(1)이다. 기껏해야 원소를 교환할 때 쓰일 임시변수 정도의 추가공간만 필요하므로 in-place 정렬이다.
• 평균과 최악의 시간복잡도는 O(n^2)이다.
• 삽입 정렬은 중복된 키 값의 순서가 정렬 후에도 유지되므로 stable 정렬이다.
• 선택 정렬이나 버블 정렬에 비해 상대적으로 빠르다.

소스코드

# include <stdio.h>
# define LEN 5

void insertionSort(int* arr){
  int i, j, key;

  for(i=1; i< LEN; i++){
    key = arr[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사

    for(j=i-1; j>=0 && arr[j]>key; j--){ // key가 더 큰 값일 때까지 
      arr[j+1] = arr[j]; // 한 칸 뒤로 이동 
    }

    arr[j+1] = key; // 알맞은 위치에 key 삽입 
  }
}

int main(){
    int arr[LEN] = {7,5,1,4,3};
    int i;
    printf("정렬 전 : ");
    for(i=0; i<5; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    insertionSort(arr);
    printf("정렬 후 : ");
    for(i=0; i<5; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");    
    
    return 0; 
}