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

 

 

 

삽입 정렬 알고리즘

삽입 정렬은 안정 정렬(중복된 값이 입력 순서 혹은 정렬 전 순서와 동일하게 정렬)에 속하며, 
다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬입니다.

 

알고리즘을 알아보기 전 대략적인 개념을 잡아보겠습니다.

 

퀵 정렬에서는 '이미 정렬된 배열' 이라는 개념을 사용하여 정렬을 수행합니다.

이미 정렬된 배열에 원소 하나를 삽입하는 것은 배열의 마지막 혹은 처음부터 순차적으로 탐색하여 

 

 

 

 

 

 

 

알고리즘은 대략 다음과 같이 이루어집니다.

1. 배열을 두 부분으로 나눕니다. 왼쪽 배열은 '정렬된 배열', 오른쪽 배열은 '정렬되지 않은 배열'입니다
2. 최초 상태에서 정렬된 배열의 길이는 1입니다.
3. '정렬되지 않은 배열'의 최좌측 원소를 선택하여 '정렬된 배열'에 삽입될 위치를 찾아 삽입합니다.
   1. 해당 과정에서 순차 탐색을 사용할 수 있습니다.
   2. 순차 탐색 대신 이분 탐색을 사용하면 성능을 더 개선시킬 수 있습니다.
4. 3번의 과정을 반복하여 배열을 정렬시킵니다.

 

 

 

 

 

 

 

 

삽입 정렬의 과정 살펴보기

다음은 배열의 초기 상태입니다.

 

 

 

 

 

 

배열을 두 부분으로 나눕니다.
왼쪽 배열은 정렬된 배열, 오른쪽 배열은 정렬되지 않은 배열이며, 초기 상태에서 정렬된 배열의 길이는 1입니다.

 

 

 

 

 

 

'정렬되지 않은 배열'의 최좌측 원소를 선택하여 '정렬된 배열'에 삽입될 위치를 찾아 삽입합니다.

 

이제 위 과정을 반복하겠습니다.

 

 

 

 

 

 

 

 

 

자바로 구현

public void insertionSort (int []arr) {

    for (int i = 1; i < arr.length; i++ ) {//정렬되지 않은 배열은 1부터 시작
       int insert = arr[i];//삽입될 원소
       int idx = i - 1;

       while ( idx >= 0 && insert < arr[idx] ){
         arr[idx + 1] = arr[idx];
         idx--;
       }
       arr[idx + 1] = insert;
    }
   }

 

 

 

 

 

 

 

 

 

 

 

 

삽입 정렬 알고리즘 특징

삽입 정렬 알고리즘은 '이미 정렬된 배열'에 대하여 속도가 매우 빠릅니다.

이미 정렬된 배열이라면 원소의 위치 교환이 발생하지 않고, $1 + 2 +  ... + n$ 번의 비교만 이루어지므로 시간복잡도는 $O(n)$ 으로 굉장히 빠릅니다.

 

그러나 평균적으로 시간 복잡도는 $O(n^{2})$ 이므로, 일반적인 경우 효율적이지는 못합니다.

 

 

 

 

 

 

 

 

다른 정렬 알고리즘과의 시간복잡도 비교

	최선의 경우	평균적인 경우	최악의 경우
선택정렬	$$O(n^{2})$$	$$O(n^{2})$$	$$O(n^{2})$$
버블정렬	$$O(n^{2})$$	$$O(n^{2})$$	$$O(n^{2})$$
삽입정렬	$$O(n)$$	$$O(n^{2})$$	$$O(n^{2})$$
퀵 정렬	$$O(n \; log(n))$$	$$O(n \; log(n))$$	$$O(n^{2})$$
힙 정렬	$$O(n \; log(n))$$	$$O(n \; log(n))$$	$$O(n \; log(n))$$
병합정렬	$$O(n \; log(n))$$	$$O(n \; log(n))$$	$$O(n \; log(n))$$