삽입 정렬

삽입 정렬(Insertion Sort)은 배열의 각 원소를 이미 정렬된 부분 배열과 비교하며 적절한 위치에 삽입해가며 정렬하는 알고리즘입니다.

이 알고리즘을 파이썬 코드로 구현하면, 우선 배열의 첫 번째 원소는 이미 정렬된 것으로 간주하고, 두 번째 원소부터 시작합니다. 배열의 i번째 원소를 적절한 위치에 삽입하려면, i 이전의 원소들과 비교하면서 삽입할 위치를 찾아가야 합니다. 이후 해당 위치에 i번째 원소를 삽입합니다. 이 과정을 모든 원소가 정렬될 때까지 반복합니다.

예를 들어, [3, 1, 5, 2, 4]라는 배열이 있다면, 우선 첫 번째 원소인 3은 이미 정렬된 것으로 간주합니다. 이후 두 번째 원소인 1을 3과 비교하면서 적절한 위치를 찾아가며 [1, 3, 5, 2, 4]가 됩니다. 이후 세 번째 원소인 5를 적절한 위치에 삽입하면 [1, 3, 5, 2, 4]가 됩니다. 이와 같은 방식으로 모든 원소를 삽입하여 정렬을 완료합니다.

파이썬 소스 코드는 다음과 같습니다.

 

def insertion_sort(insertionArr):
	n = len(insertionArr)
	# 두 번째 원소부터 시작하여 모든 원소를 순회
	for i in range(1, n):
    	key = insertionArr[i]
    	j = i - 1
    
        # 이미 정렬된 부분 배열과 비교하며 적절한 위치에 삽입
        while j >= 0 and key < insertionArr[j]:
            insertionArr[j+1] = insertionArr[j]
            j -= 1
        insertionArr[j+1] = key

	return insertionArr

 

시간 복잡도
삽입 정렬의 최선의 경우 시간 복잡도는 O(n)이고, 평균 및 최악의 경우 O(n^2)입니다. 이는 이미 정렬된 배열이라면 비교연산이 일어나지 않고, 모든 원소를 비교해야 한다면 n-1번의 비교를 수행하므로 n(n-1)/2 번의 비교를 수행하기 때문입니다.

공간 복잡도
삽입 정렬의 공간 복잡도는 O(1)입니다.