삽입정렬(Insertion Sort)

삽입 정렬( insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘인데  버블정렬(Bubble Sort)와 선택정렬(Selection Sort)와 마찬가지로 단순하고 이해하기 쉽지만 성능상으로는 느린  정렬 알고리즘 중 하나이다.

 

어떤 식으로 동작하는지 살펴보자.

 

위와 같이 정렬되지 않은 데이터들이 있고 오름차순(ascending)으로 정렬하는 것을 가정하고 설명하겠다.

 

 

삽입정렬은 처음 2개의 원소들을 비교한다.

 

14와 33 2개의 원소를 비교하면 이미 오른차순으로 정렬되어 있고  정렬 서브리스트(sorted sub-list) 14를 가지게 된다.

 

 

이제 앞으로 이동하여 33과 27을 비교한다.

 

33이 27보다 크므로 오름차순으로 정렬시 올바른 위치가 아님을 알 수 있다.

 

33과 27을 스왑한다. 또한 정렬된 서브리스트(sorted sub-list)의 모든 원소들과도 체크해본다.

지금까지 정렬된 서브리스스트가 가진 원소는 14밖에 없다. 
27은 14보다 크므로 정렬된 서브리스트내에 스왑은 불필요하다.

 

 

지금까지 우리는 14, 27을 정렬된 서브리스트로 가지고 있다.  다음에는 33과  10을 비교한다.

 

 

10은 33보다 작으므로 정렬된 순서가 아니다.

 

 따라서 33과 10을 스왑한다.

 

그러나 33과 10을 스왑한 후 정렬된 서브리스트 내 27과 10은 정렬되지 않은 상태가 되어버린다.

 

정렬된 서브 리스트와 비교해보니 10은 27보다 크므로 스왑이 필요하니 둘을 스왑한다.

 

다시 14와 10이 정렬되지 않은 상태이다.

 

다시 14와 10을 스왑한다. 결국 아래 그림처럼 정렬된 서브리스트를 얻을 수 있다.

 

 

이 과정을 정렬되지 않은 모든 값들이 정렬된 서브리트스에 정렬이 될때까지 반복하면 최종적으로 모든 원소가 오름차순으로 정렬된다.

 

▲ [출처] https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm  

 

 

아래 그림은 코드로 구현시 이해하기 쉽게하기 위해 알고리즘을 종합적으로 설명한 것인데

아이템 4를  k-1 정렬된 서브리스트(sorted sub-list)에 추가(insert)될 위치를 구하기 위해서 정렬된 서브리스트의 맨 끝(8)부터 하나씩 비교하면서 자신보다 작은 값(3)이 나타날 때까지 한칸식 쉬프트하여 최종적으로 4가 들어갈 자리를 얻게 되는 것이다. 

 

▲[출처] [알고리즘] 제3강 기본적인 정렬 알고리즘  

 

삽입정렬은 정렬된 리스트에 삽입될 위치를 찾아 가기 위해 운이 좋은 경우 한번만 비교해도 되지만 최악의 경우에는 맨 앞끼지 비교하여 찾아야 하기 때문에 선택, 버블정렬보다 평균적으로 빠르지만 최악의 경우에 O(N²)이 걸린다.

 

 
public class Main {
 
    public static void main(String[] args)  {
 
        int array[] = {14, 33, 27, 10, 35, 19, 42, 44};
        insertionSort(array);
 
        for (int i = 0 ;i < array.length ; i++){
            System.out.print(array[i] + " ");
        }
    }
 
 
    public static void insertionSort(int[] list) {
 
        // 이미 첫번재는 정렬된 서브리스트(sorted sub-list or sorted partial list)
        // 이기 때문에 루프는 1부터 시작해도 된다.
        for(int i  = 1 ; i < list.length ; i++) {
 
            int temp = list[i];
            // sorted partial list 뒤부터 하나씩 비교하여
            // temp 보다 크다면 한칸식 오른쪽으로 shift 한다.
            int k = i - 1;
            while( (k >= 0) && (list[k] > temp)) {
                list[k+1] = list[k];
                k--;
            }
            // while-loop가 끝나게 되면
            // 최종적으로 k는 temp 보다 작은 값을 가진 위치이기 때문에
            // k+1에 temp 값을 insert 해준다.
            list[k+1] = temp;
 
        }
    }
 
}