Insertion Sort

• 개념 : 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 특징
  • 현재 선택된 데이터의 앞 부분은 이미 정렬됨.
• 장점
  • 안정한 정렬 방법
  • 레코드 수 적으면 간단해서 유리
  • 대부분 이미 정렬되어있으면 효율적일수도 있다.
• 단점
  • 비교적 많은 레코드의 이동을 포함
  • 레코드 수 많고 크면 부적합
• 시간복잡도 : $O(n)$ (이동 없이 한 번의 비교만 이뤄지는 최선의 경우) / $O(n^2)$ (역순일 경우)
• 공간복잡도 : $O(1)$

선택정렬과 삽입 정렬의 유사한 점과 차이점
유사점 : k번째 반복 이후, 첫번째 k 요소가 정렬된 순서로 온다는 점
차이점 : 선택정렬은 k+1번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만 삽입정렬은 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행된다.

arr = [4,2,5,6,1,3]

# Solution 1
for i in range(1, len(arr)):
    for j in range(i, 0, -1):
        if arr[j - 1] > arr[j]:
            arr[j - 1], arr[j] = arr[j], arr[j - 1]
        else:  # 추가된 부분
            break
    print(arr)

#[2, 4, 5, 6, 1, 3]
#[2, 4, 5, 6, 1, 3]
#[2, 4, 5, 6, 1, 3]
#[1, 2, 4, 5, 6, 3]
#[1, 2, 3, 4, 5, 6]

# Solution 2
for i in range(1, len(arr)):
    j = i
    while j>0 and arr[j-1] > arr[j]:
        arr[j-1], arr[j] = arr[j], arr[j-1]
        j -= 1
    print(arr)