삽입 정렬(Insertion Sort)

개념

삽입 정렬은 2번째 원소부터 시작하여 모든 요소를 차례대로 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

 

과정

1. 2번째 위치(index)의 값을 temp에 저장한다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나간다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.

 

구현(Java)

void insertionSort(int[] arr){
   for(int index = 1; index < arr.length; index++){ // 첫번째 값의 왼쪽에는 값이 없기에 두번째 위치부터 시작
      int temp = arr[index]; // 선택값
      int prev = index - 1; // 비교위치
      while( (prev >= 0) && (arr[prev] > temp) ) { // 이전 위치가 음수가 아니며, 비교값이 선택값보다 크다면
         arr[prev+1] = arr[prev];  // 값이 하나씩 뒤로 밀림
         prev--;
      }
      arr[prev + 1] = temp; // 맞는 위치에 값을 삽입
   }
   System.out.println(Arrays.toString(arr));
}

 

시간복잡도

최악의 경우(역으로 정렬) 선택 정렬과 마찬가지로, (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 즉, O(n^2) 이다.

하지만, 모두 정렬이 되어있는 경우(Optimal)한 경우, 한번씩 밖에 비교를 안하므로 O(n) 의 시간복잡도를 가지게 된다.

 

즉, 최선의 경우는 O(n) 의 시간복잡도를 갖고, 최악의 경우 O(n^2) 의 시간복잡도를 갖게 된다.

 

 

비교

같은 시간 복잡도 O(n^2)를 가진 선택 정렬, 버블 정렬과 비교해보면 우수하다.

 

 

 

 

 

 

 

 

---

 

참고 

https://gyoogle.dev/blog/algorithm/Insertion%20Sort.html

https://ssdragon.tistory.com/112