# 선택정렬보다 효율적. // 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입함.
# 삽입정렬도 O(N^2)의 시간복잡도. 마찬가지로 반복문 두번 중첩
# 현재 리스트의 데이터가  거의 정렬돼있는 상태면 매우 빠르게 동작한다. -> 최선의 경우 O(n)의 시간복잡도

""" 첫 원소는 이미 정렬되어있다고 생각한다. 두 번 째 원소부터, 들어가야 할 위치를 앞쪽에서 찾은 후(비교) , 위치를 바꿔준다."""

data = [9, 3, 5, 6, 2, 1, 8, 4, 7,100,0.3, 1251, 99, 45,32,5412]

for i in range(1, len(data)):
    for j in range(i, 0, -1):
        if data[j] < data[j-1]:
            data[j], data[j-1] = data[j-1], data[j]
        # else문을 안 넣어줘도 결과적으로는 상관이 없지만, 이미 들어갈 자리를 찾은 상태에서 의미없는 연산을 꽤나 많이 해야한다.
        else:
            break


print(data)