[알고리즘] 삽입 정렬이란? (개념, 파이썬 코드)

삽입 정렬(Insertion Sort)이란?

원소를 하나씩 확인하면서, 각 원소를 적절한 위치에 삽입하는 알고리즘

• 방법
  • 2번째 원소부터 시작한다.
  • 해당 원소의 왼쪽으로 하나씩 확인하면서, 자신보다 작은 원소가 존재하는 경우 그 오른쪽에 삽입한다.
    자신보다 큰 원소인 경우 오른쪽으로 한 칸 밀고, 다음 원소를 확인한다.
  • 위 작업을 n번째 원소까지 반복한다.

 

파이썬으로 구현하기

def insertion_sort(arr):
    n = len(arr)

    for i in range(1, n):  # arr[i]의 위치를 찾는다.
        for j in range(i, 0, -1):
            if arr[j] < arr[j-1]:  # 자신(arr[j])보다 더 큰 원소인 경우, 큰 원소를 오른쪽으로 한 칸 이동시킨다.
                arr[j], arr[j-1] = arr[j-1], arr[j]
            else:
                break

if __name__ == "__main__":
    arr = [1,6,4,2,3,5]

    print(f"before : {arr}")  # 정렬 전 리스트
    insertion_sort(arr)
    print(f"after : {arr}")  # 정렬 후 리스트

 

시간복잡도

입력 리스트의 원소가 n개인 경우,

삽입 정렬의 연산 횟수는 아래와 같다.

• 2번째 원소 : 최대 1번
• 3번째 원소 : 최대 2번
• ...
• n번째 원소 : 최대 n-1번

(n-1) + (n-2) + ... + 1 = (n-1)(n-2)/2 이므로,

O(n^2)의 시간이 소요된다.