[Algorithm] 삽입 정렬

1. 삽입정렬 개념
2. 구현 코드
3. 시간 복잡도

---

삽입 정렬 Insertion Sort 란?

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 알고리즘

손안의 카드를 정렬하는 방법과 유사

처음 Key 값은 두 번째 자료부터 시작

 

구현 코드

def insertion_sort(arr):
	for i in range(1, len(arr)):
            key = arr[i]
            j = i-1
            # key가 정렬된 부분에서 적절한 위치를 찾을 때까지 비교하고 이동
            while j >= 0 and key < arr[j]: # key보다 큰 요소들을 오른쪽으로 이동
                arr[j+1] = arr[j] # 요소를 오른쪽으로 이동
                j -= 1 # 인덱스를 한 칸 왼쪽으로 이동
            # 적절한 위치에 key 삽입
            arr[j+1] = key

 

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

 

최선의 경우

• 이동 없이 1번의 비교만 이루어짐
• 외부 루프 : (n-1)번
• Best T(n) = O(n)

최악의 경우(입력 자료가 역순일 경우)

• 외부 루프 안의 각 반복마다 i번의 비교 수행
• 외부 루프 : (n-1)+ (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)
• Worst T(n) = O(n^2)