[정렬] Insertion Sort(삽입 정렬) 기본 개념 및 관련 문제 풀기!

이번 포스트에서는 정렬 알고리즘 중에 하나인 Insertion Sort에 대해서 알아보겠습니다.

개념 소개 

Insertion Sort는 번역하면 삽입 정렬이라고 합니다.

 

삽입 정렬은 배열을 처음부터 순회하면서 해당 원소가 들어가야할 자리를 찾아서 삽입시키는 방법을 의미합니다. 삽입 정렬에서 중요한 것은 바로 자신의 앞 배열이 모두 정렬되어 있다는 것입니다. 예를 들어서 현재 삽입해야할 원소가 3번째 원소라면, 반드시 1번과 2번 원소는 정렬이 되어 있어야합니다. 그래야만 3번째 원소가 어디에 들어가야하는지를 찾을 수 있습니다.

 

예시를 함께 보겠습니다.

 

배열 [5, 4, 2, 3, 1] 이 있다고 가정해보겠습니다. 

첫번째 원소인 5는 앞에 원소가 없이 자기 자신뿐이므로 그 자체로 정렬이 되어있다고 볼 수 있습니다. 숫자가 1개만 있다면 그 수는 존재 자체만으로 이미 정렬이 되어 있는 것입니다. 

 

 

두번째 원소 [4] 순서

   - [5, 4] 배열만 보시면 됩니다. 4는 5보다 작기 때문에 4는 5 앞에 삽입되어야 합니다. 즉, 4 와 5 의 순서를 바꾸어서 [4, 5] 가 됩니다.

 

세번째 원소 [2] 순서

   - [4, 5, 2] 배열만 보시면 됩니다. 2 앞에 있는 [4, 5] 는 바로 위에서 이미 정렬이 되었습니다. 이제 2가 들어갈 위치만 찾으면 됩니다.

   - 2 < 5 이므로, 2와 5의 순서를 바꾸면 배열은 [4, 2, 5] 가 됩니다.

   - 2 < 4 이므로, 2와 4의 순서를 바꾸면 배열은 [2, 4, 5] 가 됩니다.

 

이렇게 순서를 계속 바꾸어 나가면 아래와 같은 순서로 배열이 정렬 됩니다.

빨간색은 이미 정렬된 부분입니다.

       [5, 4, 2, 3, 1]

--> [4, 5, 2, 3, 1]

--> [2, 4, 5, 3, 1]

--> [2, 3, 4, 5, 1]

--> [1, 2, 3, 4, 5]

 

 

Python으로 알고리즘을 구현하면 다음과 같습니다.

def insertionSort(nums: List[int]) -> List[int]:

    # Insertion Sort를 활용하여 문제 풀기
    # 첫번째 원소는 이미 정렬되어 있으므로, 두 번째 원소부터 진행합니다.
    for i in range(1, len(nums)):
        # i-1 부터 0까지 역순으로 순회하면서 자신이 들어갈 위치를 찾습니다.
        for j in range(i-1, -1, -1):
            # 만약 자신보다 큰 수가 나오면 위치를 변경합니다.
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
            
            # 그렇지 않으면 더 이상 비교할 필요가 없으므로 현재 위치가 올바르게 삽입된 위치입니다.
            # Break로 나올 수 있는 이유는 0 ~ i-1번째는 이미 앞에서 정렬이 마쳐진 상태이기 때문입니다.
            else:
                break

    return nums

 

위 함수를 실행시켜보겠습니다.

변화되는 부분을 보기 위해서 For문이 끝날때마다 배열을 출력해보겠습니다.

위에서 보시던 것과 같은 순서로 결과가 출력되는 것을 보실 수 있습니다.

 

복잡도

시간 복잡도: O(N^2)

InsertionSort는 매 원소마다 앞부분의 원소들을 체크해야합니다. 최악의 경우 배열이 역순이었다면, 모든 원소를 조사할 때마다 변경이 발생합니다. 따라서 배열의 길이가 N이라고 하면 O(N^2)의 시간 복잡도가 발생합니다.

 

공간 복잡도: O(1)

InsertionSort는 추가로 배열을 사용하지 않고, 주어진 배열을 그대로 사용하기 때문에 별도의 공간 할당이 없습니다. 따라서 O(1)의 공간 복잡도를 갖습니다.

 

 

관련 문제

사실 InsertionSort는 배열을 정렬하는 문제라면 어느 곳에서든 사용할 수 있습니다. 다만 입력이 양을 제곱했을 때 1억이 넘어가게 되면 시간 초과로 틀리게 됩니다. 즉, 알고리즘을 알고 있어도 문제는 통과하지 못할 수 있습니다.

 

내장된 Sort기능을 사용하지 않고 배열을 Sort해보는 문제인데, 위 코드를 넣어서 풀면 예시는 전부 정답이 나오고 결과는 Time Limit Exceeded가 나올겁니다. 

Sort an Array - LeetCode

 

틀려도 괜찮습니다. 알고리즘을 이해하는 것이 중요합니다. 현업에서 InsertionSort를 사용한 코드를 보고 이해할 수 있다면 성공입니다.

다음에 배울 더 빠른 배열 방법을 쓰는 해당 문제는 풀 수 있습니다.