[파이썬][알고리즘] 삽입 정렬

삽입 정렬

삽입 정렬 (insertion sort)

• 2번째 인덱스부터 시작해서 앞의 숫자를 비교.
• 비교 숫자보다 크면 자리를 바꿈
  • 작은 숫자가 나오면 멈춤
  • 참조 (visualgo.net/en/sorting)

데이터가 2개 일 때

• index 1과 index 0 만 비교
  
  

데이터가 3개일 때

데이터가 4개일 때

def insertion_sort(data):
    for trial in range(len(data) - 1):
        for i in range(trial + 1, 0, -1):
            if data[i] < data[i - 1]:
                data[i], data[i - 1] = data[i - 1], data[i]
            else:
                break
    return data

import random

num = random.sample(range(100), 10)
print(num)
print(insertion_sort(num))

[29, 62, 11, 37, 1, 66, 80, 28, 0, 44]
[0, 1, 11, 28, 29, 37, 44, 62, 66, 80]

시간 복잡도

• O($n^2$)
• 완전 정렬되어 있으면 O(n)