삽입 정렬(Insertion Sort)

해당 글은 gyoogle 님 github를 참고해서 작성한 글입니다.

GimunLee/tech-refrigerator

 

 

삽입 정렬(Insertion Sort)

 

Abstract

손 안의 카드를 정렬하는 방법과 유사합니다.

Insertion Sort는 Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘입니다.

Insertion Sort는 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘입니다.

최선의 경우 $O(n)$이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘입니다.

 

Process

1. 정렬은 2번째 위치(index)의 값을 temp에 저장합니다.
2. temp와 이전에 있는 원소들과 비교하여 삽입해나갑니다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복합니다.

 

Python Code

def insertionSort(arr:list):

    for i in range(1, len(arr)):		# 1.
        prev = i - 1
        temp = arr[i]
        while prev >= 0 and arr[prev] > temp:			# 2.
            arr[prev+1] = arr[prev]
            prev -= 1
                
        arr[prev+1] = temp				# 3.

    return arr

1. 첫 번째 원소 앞(왼쪽)에는 어떤 원소도 갖고 있지 않기 때문에, 두 번째 위치(index)부터 탐색을 시작합니다. temp에 임시로 해당 위치(index) 값을 저장하고, prev에는 해당 위치(index)의 이전 위치(index)를 저장합니다.
2. 이전 위치(index)를 가리키는 prev가 음수가 되지 않고, 이전 위치(index)의 값이 '1'번에서 선택한 값보다 크다면, 서로 값을 교환해주고 prev를 더 이전 위치(index)를 가리키도록 합니다.
3. '2'번에서 반복문이 끝나고 난 뒤, prev에는 현재 temp 값보다 작은 값들 중 제일 큰 값의 위치(index)를 가리키게 됩니다. 따라서, (prev+1)에 temp 값을 삽입해줍니다.

 

시간 복잡도

최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로, (n-1) + (n-2) + ... + 2 + 1 -> n(n-1)/2 즉, $O(n^2)$입니다.

하지만, 모두 정렬이 되어있는 경우(Optimal)한 경우, 한 번씩 밖에 비교를 안 하므로 $O(n)$의 시간 복잡도를 가지게 됩니다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문입니다.

 

최선의 경우는 $O(n)$의 시간복잡도를 갖고, 평균과 최악의 경우 $O(n^2)$의 시간 복잡도를 갖게 됩니다.

 

위의 코드를 자세히 살펴보면,

1. for문 n-1번 반복
2. prev 입력, temp 입력
3. while문 1, 2, .... 최대 n-1번 반복
4. prev값을 prev+1로 이동, prev - 1
5. 적절한 위치에 temp값 입력
6. 계산해보면 $\Sigma^{n-1}{(O(1)+O(1)+ (\Sigma^{n-1}{O(1)+O(1)}) + O(1))}$
7. 결과적으로, $O(n^2)$

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 $O(n)$ 입니다.

 

장점 & 단점

1. 장점
   • 알고리즘이 단순합니다.
   • 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있습니다.
   • 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. -> 제자리 정렬(in-place sorting)
   • 안정 정렬(Stable Sort)
   • Selection Sort나 Bubble Sort와 같은 $O(n^2)$ 알고리즘에 비교하여 상대적으로 빠릅니다.
2. 단점
   • 평균과 최악의 시간 복잡도가 $O(n^2)$으로 비효율적입니다.
   • Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적입니다.

Conclusion

Selection Sort와 Insertion Sort는 k번째 반복 이후, 첫 번째 k요소가 정렬된 순서로 온다는 점에서 유사합니다. 하지만, Selection Sort는 k+1번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만 Insertion Sort는 k+1번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행된다는 차이가 있습니다.