삽입 정렬(insertion sort)

삽입 정렬

• 적절한 위치에 삽입한다.
• 버블 정렬, 선택 정렬보다 빠르다.
• 삽입 정렬은 옆의 값과 비교해서 더 클 때만 스위칭하기 때문에 더 빠르다.

• 특정한 경우에 굉장히 빠르게 작용할 수 있다. ( 예 : 거의 정렬되어 있는 데이터일 때 )

 

시간 복잡도    =>    O(N^2)

 

동작 원리

- 특정한 위치에서 앞의 원소들과 비교해서 적당한 위치에 들어간다.

ex) 1 5 6 7 8 10 4 3 2 9   

     => 4가 적절한 위치에 들어갈 때 이미 앞 부분은 다 정렬이 되어 있기 때문에 4만 앞의 원소들과 하나씩
          비교해가며 들어가면 되기 때문에 매번 비교할 때마다 선택이나 버블처럼 교환하지 않아도 된다.
   

     1 5 6 7 8 4 10 3 2 9  ->  4와 8 비교해서 자리 바꿈
     1 5 6 7 4 8 10 3 2 9  ->  4와 7 비교해서 자리 바꿈
     1 5 6 4 7 8 10 3 2 9  ->  4와 6 비교해서 자리 바꿈
     1 5 4 6 7 8 10 3 2 9  ->  4와 5 비교해서 자리 바꿈
     1 4 5 6 7 8 10 3 2 9  ->  1과 4 비교해서 4가 더 크므로 여기서 정지 ( 멈출 때에 정지할 수 있다는게 장점 )
  

삽입 정렬 코드

#include<stdio.h>

int main(){
  int i,j,temp;
  int array[10]={1,10,5,8,6,5,4,3,2,9};
  for(i = 0;i < 9; i++){
    j = i;
    while(array[j] > array[j+1]){
      temp = array[j];
      array[j] =  array[j+1];
      array[j+1] = temp;
      j--;
    }
    printf("\n");
  }

}