3.1. Sorting - 3.1.3 Insertion Sort

CS - 3. Common Algorithms - 3.1. Sorting - 3.1.3 Insertion Sort

 

💡Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

삽입 정렬은 비교를 통해 한 번에 한 항목씩 최종 정렬된 배열을 구축하는 간단한 정렬 알고리즘입니다. 퀵 정렬, 힙 정렬 또는 병합 정렬과 같은 고급 알고리즘에 비해 큰 목록에서는 효율성이 훨씬 떨어집니다.

 

삽입 정렬(Insertion Sort)는 각 숫자를 적절한 위치에 '삽입'하는 방식으로 정렬하는 알고리즘입니다.

주어진 배열을 두 부분으로 나누어, 하나는 이미 정렬된 부분이고 다른 하나는 아직 정렬되지 않은 부분으로 간주합니다.

 

삽입 정렬의 동작 과정은 이렇습니다.

1. 배열의 첫 번쨰 원소는 이미 정렬된 것으로 간주합니다.

2. 정렬되지 않은 부분의 첫 번 쨰 원소를 선택하고, 이미 정렬된 부분에서 이 원소보다 큰 원소들을 오른쪽으로 한칸 씩 이동시킵니다.

3. 이렇게 해서 빈 자리가 생기면, 선택한 원소를 그 자리에 삽입합니다.

4. 이 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다.

 

In Python

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

 

삽입 정렬의 시간 복잡도는 최악의 경우 O(n^2)입니다. 

이미 거의 정렬된 배열에서 매우 효율적으로 동작하며, 이 경우에는 거의 O(n)에 가까운 성능을 보여줍니다.

왜 그럴까요?

배열이 이미 거의 정렬된 상태라면, 각 원소를 적절한 위치에 삽입하는데 필요한 비교 횟수가 매우 적어집니다.

정확하게 이해하려면, 삽입 정렬의 동작 방식을 생각해보면 됩니다.

대부분의 원소가 이미 적절한 위치에 있으므로, 삽입할 위치를 찾기 위한 비교수가 훨씬 적어 O(n)에 가까워진다는 것.