삽입정렬(InsertionSort) 이론과 파이썬 구현

삽입정렬(InsertionSort)

 

삽입정렬은 리스트나 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눕니다.

그 후 정렬되지 않은 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입해 정렬되도록 합니다.

이 과정을 정렬되지 않은 부분이 없어질 때까지 반복하면 전체를 정렬할 수 있습니다.

 

삽입 정렬은 리스트의 상태에 따라 시간복잡도가 달라질 수 있습니다.

삽입 정렬은 거의 정렬이 되어 있는 경우에 새로운 원소를 추가할 때 다른 정렬 방법들보다 유용합니다.

 

삽입정렬을 이용한 전체 정렬 과정

 

삽입정렬의 파이썬 코드입니다.

a = [3, 2, 5, 4, 1]

for i in range(1,len(a)):
    key = a[i]
    
    j = i - 1

    while j >= 0 and a[j] > key:
        a[j+1] = a[j]
        j = j - 1

    a[j+1] = key
 
# 출력>>[1, 2, 3, 4, 5]
print(a)