Insertion sort (삽입 정렬)

선택 정렬

    - 두 번째 위치부터 시작하여, 왼쪽에 정렬된 배열과 비교하여 요소의 위치를 찾아 삽입하는 정렬

 

 

 

동작

    - 주어진 리스트 두 번째 위치부터 차례대로 요소를 선택

    - 선택한 요소를 왼쪽에 정렬된 배열과 비교하여 자신의 위치를 찾고 삽입

    - 위 과정 반복

 

    - 예시

        * 1번 : 요소 2를 선택하고 왼쪽에 정렬된 배열에서 들어갈 위치를 찾아 삽입

        * 2번 : 요소 4를 선택하고 왼쪽에 정렬된 배열에서 들어갈 위치를 찾아 삽압

        * 이하 과정 동일

 

 

구현

void insertionSort (int *list, int n){
    
    // 요소가 들어갈 위치, 요소 값
    int j, value;
    
      for(int i=1; i<n; i++){
          
        // 정렬할 값
          value = list[i];
          
        // 선택한 값의 위치-1부터 0까지 가면서 값들을 한 칸씩 뒤로 옮기기
          for(j=i-1; j>=0 && list[j] > value; j--){
              list[j+1] = list[j];
        }
        
        // 멈춘 곳에 정렬할 값 삽입
        list[j+1] = value;  
      }
      
}

 

 

특징

    - 안정한 정렬

        * 위 구현에서 선택한 값이 클 때까지 loop를 순환하므로 같은 값에서는 멈춤

        * 안정한 정렬 : [8][4][5][7][8][2]라는 배열이 있을 때, [2][4][5][7][8][8]로 정렬되어 8의 위치가 그대로 유지

        * 불안정한 정렬 : 2][4][5][7][8][8]로 정렬되어 8의 위치가 뒤바뀜

        * 안정한 정렬을 선호하는 이유 : 온라인 쇼핑 목록에서 정렬할 때를 생각해 보자. 첫 번째로 최저가 순으로 나열하고, 두 번째로 리뷰 순으로 나열한다고 하자. 안정한 정렬일 경우에는 최저가에서 리뷰 순으로 나열된다. 불안정한 정렬일 경우에 두 번째인 리뷰 순으로 나열하는 순간 첫 번째로 해놓은 최저가 순 정렬은 무용지물이 된다.

 

    - 한 번에 한 요소의 위치만 결정하기 때문에 비효율

 

    - 시간복잡도

       * 평균 : O(N^2)

       * 최악 : O(N^2)

       * 최선 : O(N)

           + 모두 정렬되어 있을 때, 왼쪽에 배열된 모든 요소들을 볼 필요가 없음

 

 

 

참조

    - 블로그 1

    - 블로그 2

    - 위키피디아