삽입 정렬

def insertion_sort(arr) :
    n = len(arr)

    # arr[0]는 정렬이 완료된 부분으로 치기 때문에 1부터 순회
    # i: 정렬된 부분과 비교할 요소의 인덱스
    for i in range(1,n) :

        # j: i, i-1 , i-2, i-3....
        # i-1: 비교할 요소가 가장 먼저 비교하게 될 정렬된 부분
        # 0~(i-1): 이미 정렬된 부분
        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
    return arr


print(insertion_sort([99,200,32,120,2,55]))