[Algorithm] 삽입 정렬(Insertion Sort) - C++, Java, Python 구현

 

 

정렬 알고리즘 중 삽입 정렬을 알아보고 C++, 자바, 파이썬으로 구현해봅시다.

 

• 자료구조, 알고리즘 시리즈 모아보기

 

삽입 정렬

`삽입 정렬(insertion sort)`은 정렬된 부분을 하나씩 확장해 가며 모든 수열을 정렬하는 알고리즘입니다. 

- Pseudocode

정렬해야 하는 배열 A[n]이 주어졌을 때 삽입 정렬 알고리즘은 다음과 같습니다.

insertionSort(A[], n){
    for( last ← 2 to n )
        A[1 ⋯ last] 에 A[last]가 들어갈 곳을 찾아 넣는다;
}

구체화하면 아래와 같습니다.

insertionSort(A[], n){
    for( last ← 2 to n ){
        newElement ← A[last]; // 추가할 요소
        i ← last-1; // newElement와 비교할 요소의 커서
        while( i ≥ 1 and newElement < A[i] ){
            A[i+1] ← A[i]; // newElement보다 큰 요소는 한칸 뒤로
            i--;
        }
        A[i+1] ← newElement; // 마지막으로 비교한 요소 자리에 newElement 추가
    }
}

선택정렬은 정렬된 부분을 늘려가는 정렬입니다. 

들어갈 자리를 만들고 넣어주는 방식입니다. while문이 끝나고 나면 i는 마지막으로 비교한 요소보다 1작습니다. 따라서 i + 1자리가 마지막으로 비교한 요소의 자리입니다.

 

- 시간 복잡도

삽입 정렬의 시간 복잡도는 $\Omicron(n^2)$입니다.

모든 경우에서 for 문은 i가 2에서 n까지 반복합니다. 각 반복마다  while문의 비교는 최대 i-1번 최소 1번 수행됩니다. 평균 적으로 $i+1\over 2$번 수행되므로 최악의 경우 $\Theta(n^2)$, 평균의 경우 $\Theta(n^2)$, 최선의 경우 $\Theta(n)$이므로 $\Omicron(n^2)$입니다.

 

구현

- C++

void insertion_sort(int arr[], int n) {
    for(int last=1; last<n; last++) {
        int x = arr[last];
        int i = last;
        while(--i >= 0 && x < arr[i]) 
            arr[i+1] = arr[i];
        arr[i+1] = x;
    }
}

- Java

class Sort {
    public static void insertionSort(int[] arr){
        for(int last=1; last<arr.length; last++){
            int newElement = arr[last];
            int i = last - 1;
            while( i >= 0 && newElement < arr[i] )
                arr[i+1] = arr[i--];
            
            arr[i+1] = newElement;
        }
    }
}

- Python

def insertion_sort(arr):
    for last in range(1, len(arr)):
        new_element = arr[last]
        i = last - 1
        while i>=0 and new_element < arr[i]:
            arr[i], arr[i+1] = arr[i+1], arr[i]
            i -= 1
        arr[i+1] = new_element