Insertion Sort

Insertion Sort(stabl sort)

리스트의 앞에서부터 이미 정렬된 서브 리스트 값들과 비교 후에 자신의 위치에 삽입을 하는 것입니다.

삽입 정렬은 인덱스 0인 부분(서브 리스트)은 이미 정렬이 되었다고 판단을 하여 인덱스 1인부분 부터 정렬을 시작합니다.

작은 값은 큰 값의 앞으로 보내지고 큰 값은 다른 큰 값이 나오기 전까지 그 위치에서 고정이 된 상태를 말합니다.

그러므로, 데이터의 이동이 많지만 리스트 내의 데이터가 어느정도 정렬이 되어있을 경우는 데이터의 이동이 적습니다.

시간복잡도는 평균적으로은 O(N^2)이지만 최선의 경우(모두 정렬)에는 O(N)이고 최악의 경우(역정렬상태)라면 O(N^2)입니다.

*예시

code

def insertion_sort(arr): #삽입 정렬
    for i in range(1, len(arr)): #인덱스 1부터 시작하는 것을 의미
        key = arr[i] #key는 곧 해당 i번째 인덱스 위치의 값
        j = i -1 #인접한 것을 비교하기에 그 전 위치의 값과 비교
        while j >= 0 and arr[j] > key: #j <0 그리고 arr[j] <=key될 때까지 하기
            arr[j + 1] = arr[j] #인덱스의 위치가  i와 j가 같을 때
            j -= 1 #한 위치 옮겨야한다
        arr[j + 1] = key # j+1의 값은 곧 key

if __name__ == "__main__": #main.py
    arr = [9,1,6,3,7,2,8,4,5,0] # 배열값
    insertion_sort(arr) #삽입 정렬 함수 구현
    print(arr) # 결과값 : [0,1,2,3,4,5,6,7,8,9]