삽입 정렬은 간단하면서도 효율적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소들을 정렬된 부분에 올바른 위치에 삽입하는 방식으로 동작합니다.

알고리즘 동작 방식

1. 배열의 첫 번째 원소는 이미 정렬되어 있다고 가정합니다.
2. 두 번째 원소부터 시작하여 차례대로 정렬되지 않은 부분을 탐색합니다.
3. 정렬되지 않은 부분의 현재 위치에 있는 원소를 정렬된 부분 내에서 올바른 위치에 삽입합니다.
4. 위의 과정을 정렬되지 않은 부분의 모든 원소가 정렬될 때까지 반복합니다.

예시 코드

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

# 테스트
array = [5, 2, 1, 4, 3]
insertion_sort(array)
print(array)  # Output: [1, 2, 3, 4, 5]

위의 예시 코드는 파이썬으로 구현된 삽입 정렬 알고리즘입니다. insertion_sort 함수는 배열을 매개변수로 받아 해당 배열을 삽입 정렬하여 수정합니다. 입력값으로 [5, 2, 1, 4, 3]를 주면 [1, 2, 3, 4, 5]로 정렬된 결과를 출력합니다.

시간 복잡도

삽입 정렬의 시간 복잡도는 평균적으로 O(n^2)입니다. 최선의 경우에는 이미 정렬된 배열을 입력으로 주는 경우로 O(n)의 시간 복잡도를 가질 수도 있습니다. 그러나 최악의 경우에는 역순으로 정렬된 배열을 입력으로 주는 경우로 O(n^2)의 시간 복잡도를 가집니다.

결론

삽입 정렬은 자료의 이동이 발생하는 횟수가 상대적으로 적으며, 구현이 간단한 장점이 있습니다. 따라서 원소의 개수가 적거나 이미 정렬된 상태에서 어느 정도 오름차순으로 정렬된 자료를 추가로 정렬할 때 유용한 알고리즘입니다.

참고 자료

• 위키백과 - 삽입 정렬
• GeeksforGeeks - Insertion Sort