Insertion Sort

정렬 과정

• 정렬할 자료를 두 개의 부분집합 S와 U로 가정

  1. 부분집합 S : 정렬된 앞부분의 원소들

  2. 부분집합 U : 아직 정렬되지 않은 나머지 원소들

• 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다.

• 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 된다.

• 부분집합 U가 공집합이 되면 삽입정렬이 완성된다

시간 복잡도

• O (n ^ 2)

  • 각 부분집합의 원소를 매번 비교해야 하므로!

Iterative Selection Sort

arr = [69, 10, 30, 2, 16, 8, 31, 22]
N = len(arr)

for i in range(1,N):  # 1 ~ N-1
    tmp = arr[i]
    print(arr[:i], arr[i:])
    j = i -1
    while j >= 0 and arr[j] > tmp:
        arr[j+1] = arr[j]
        j -= 1
    arr[j+1] = tmp

print(arr)