[알고리즘] 삽입정렬

삽입 정렬(insertion sort) 알고리즘 개념 요약

• 손안의 카드를 정렬하는 방법과 유사하다.

  • 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다.

  • 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

• 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

삽입 정렬(insertion sort) 알고리즘의 구체적인 개념

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

• 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

• 처음 Key 값은 두 번째 자료부터 시작한다.

삽입 정렬(insertion sort) 알고리즘의 예제

배열에 8, 5, 6, 2, 4가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

삽입 정렬 코드(java)

void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){ // 1.
      int temp = arr[index];
      int prev = index - 1;
      while( (prev >= 0) && (arr[prev] > temp) ) {    // 2.
         arr[prev+1] = arr[prev];
         prev--;
      }
      arr[prev + 1] = temp;                           // 3.
   }
   System.out.println(Arrays.toString(arr));
}

시간복잡도

시간복잡도를 계산한다면

• 최선의 경우
  • 비교 횟수
  • 이동 없이 1번의 비교만 이루어진다.
  • 외부 루프: (n-1)번
  • Best T(n) = O(n)
• 최악의 경우(입력 자료가 역순일 경우)
  • 비교 횟수
  • 외부 루프 안의 각 반복마다 i번의 비교 수행
  • 외부 루프: (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O($n^2$)
• 교환 횟수
  • 외부 루프의 각 단계마다 (i+2)번의 이동 발생
  • n(n-1)/2 + 2(n-1) = (n^2+3n-4)/2 = O($n^2$)
• Worst T(n) = O($n^2$)

삽입 정렬의 장단점

장점​

• 알고리즘이 단순하다.
• 추가적인 메모리 소비가 작다.
• 거의 정렬 된 경우 매우 효율적이고 최선의 경우 O(N)의 시간복잡도를 갖는다.
• 안정 정렬이 가능하다.

단점​

• 비교적 많은 수들의 이동을 포함하며 비교할 수가 많고 크기가 클 경우에 적합하지 않다.
• 최악의 경우 O(N^2)의 시간복잡도를 갖는다.
• 데이터의 상태에 따라서 성능 편차가 매우 크다.

참고

https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/%EC%82%BD%EC%9E%85%20%EC%A0%95%EB%A0%AC%20(Insertion%20Sort).md#%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC-insertion-sort
https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html