삽입정렬(InsertionSort)이란?

삽입정렬

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

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

두번 째 원소인 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; 
}


출처: https://code-lab1.tistory.com/22?category=1213003 [code_lab]

실행결과