[Algorithm] 삽입 정렬 (python)

삽입 정렬

삽입 정렬은, 요소를 올바른 위치에 삽입해 정렬하는 방식으로, 자리 변경이 필요할 때만 위치를 변경하므로 효과적이다!

input = [4, 6, 2, 9, 1]

# 삽입 정렬
def insertion_sort(array):
    n = len(array)
    for i in range(1, n):   # 0번째는 이미 정렬되어 있는 상태라 순회필요x
        for j in range(i):
            # 앞 데이터가 더 크면 변경이 필
            if array[i-j-1] > array[i-j]:  # 주어진 데이터의 뒤에서 부터 앞으로 검사
                array[i-j-1], array[i-j] = array[i-j], array[i-j-1]
            # 뒤 데이터가 더 크면 변경 필요가 x -> 반복문 돌 필요가 없음
            else:
                break
    return array

insertion_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))

• 0번째는 이미 정렬되어 있는 상태이므로 1번째부터 순회하도록 했다
• 반복문 순회는 역순으로 비교하며, 최소값을 가장 앞으로 보내도록 구현했다
• 자리변경이 필요없는 경우엔 break로 반복문 탈출!

[출력]
[1, 2, 4, 6, 9]
정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 =  [4, 5, 7, 7, 8]
정답 = [-1, 3, 9, 17] / 현재 풀이 값 =  [-1, 3, 9, 17]
정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 =  [-3, 32, 44, 56, 100]

시간 복잡도

• O(n^2)
  • 반복문을 2중으로 사용하기 때문
  • 다른 정렬 알고리즘과 다르게, 베스트케이스에선 $Ω(n)$ 시간복잡도가 걸린다.
    • 정렬이 되어있는 상태라면? 자리변경이 필요없고 반복문을 돌지 않음