삽입 정렬 Insertion Sort

데이터가 들어갈 위치를 찾아서 해당 위치에 삽입!
보통의 경우 O(N^2)의 시간 복잡도!

거의 정렬된 리스트에 한에서 최강의 효율을 낸다.
O(N)에 가깝게...!

for i in range(len(array)):
    for j in range(i, 0, -1):
        if array[j] < array[j-1]:
            # 원소 밀어내기
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break

if array[j] < array[j-1]:
     # 원소 밀어내기
     array[j], array[j-1] = array[j-1], array[j]
else:
     break
 바로 앞의 원소와 비교하여 조건을 만족하면 앞의 원소를 밀어내고
 (j번째 원소가 다시 j-1번째 원소가 되는 것..)
 다음 원소와 계속해서 비교한다.
 조건을 만족하지 않는 경우를 만나면 반복을 종료하게 된다.
 j-1 앞의 원소들은 j-1보다 작을것이 보장되어 있으니까!

Best Case, Worst Case 사이의 시간 복잡도 갭이 크다?

주어진 문제의 데이터가 거진 정렬되어 있다면, 그 상황에서 정렬해야한다면...
O(NlogN) 정렬 알고리즘들 보다 효율적일 수 있다는 점을 기억하자!

‹ 정렬 알고리즘 목록으로