삽입정렬(Insertion Sort) 알고리즘

삽입정렬 알고리즘 개념

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

삽입정렬 알고리즘의 과정

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

삽입정렬 예시

삽입정렬 알고리즘 구현 코드 - JAVA

void insertionSort(int[] arr)
{

   for(int i = 1 ; i < arr.length ; i++){

      int temp = arr[i];
      int aux = i - 1;

      while( (aux >= 0) && ( arr[aux] > temp ) ) {

         arr[aux+1] = arr[aux];
         aux--;
      }
      arr[aux + 1] = temp;
   }
}

삽입정렬 알고리즘의 시간복잡도

1. 최선의 경우
   : 이동 없이 한번의 비교만 발생한다.
   : 외부 루프 (n-1)번

   O(n)

2. 최악의 경우
   : 입력 자료가 역순일 경우

   O(n^2)

삽입정렬 알고리즘의 장점

1. 구현이 간단하다.
2. 안정적이다.
3. 배열이 짧을수록 알고리즘 자체가 매우 간단하므로 다른 정렬 방법보다 유리할 수 있다.
4. 대부분의 레코드가 정렬되어 있을수록 효율적이다.

삽입정렬 알고리즘의 단점

1. 배열이 길어질수록 효율이 떨어진다.
2. 비교적 많은 레코드들의 이동을 포함한다.

참고

https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC
https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html