[Algorithm] Insertion Sort(삽입 정렬)

[Algorithm] Insertion Sort(삽입 정렬)

 

1. 정의

• 2번째 원소부터 시작하여 그 앞의 원소들과 대소비교하여 삽입할 위치를 결정하여 삽입
• Selection Sort와 유사하지만, 좀 더 효율적인 알고리즘
• 시간복잡도
  • 최선 : $O(n)$ → 모두 다 정렬되어 있을 경우
  • 평균 : $O(n^2)$
  • 최악 : $O(n^2)$

2. 동작 과정(오름차순)

1. 2번째 인덱스 값을 tmp에 저장
2. tmp 앞에 있는 원소들과 비교하여 가장 알맞은 자리(arr[i] < arr[tmp] < arr[i + 1])에 삽입 → 삽입하는 자리는 뒤로 한칸씩 밀린다.
3. 1번으로 돌아가 반복

3. 장단점

• 장점
  • 알고리즘이 단순
  • 정렬되어 있을 경우 매우 효율적
  • 제자리 정렬
  • 안정 정렬
• 단점
  • 평균과 최악의 시간복잡도가 $O(n^2)$이므로 비효율적
  • 배열의 길이 길어질수록 비효율적

4. 코드

void insertionsSort(int[] arr) {
   for (int i = 1; i < arr.length; i++) {
      int tmp = arr[i];
      int prev = i - 1;

      while ((prev >= 0) && (arr[prev] > tmp)) {
         arr[prev + 1] = arr[prev];
         prev--;
      }
      arr[prev + 1] = tmp;
   }
}

---

※ 참고

• tech-refrigerator 삽입 정렬 (Insertion Sort)
• [알고리즘] 삽입 정렬(insertion sort)이란
• 삽입정렬 - 위키피디아