[알고리즘] 삽입 정렬(Insertion Sort)

삽입 정렬(insertion sort)란?

• 데이터를 하나씩 확인하면서 , 각 데이터를 적절한 위치에 삽입 하는 정렬 방법이다. 더불어 삽입 정렬은 특정한 데이터가 정렬 되기 이전에 앞까지의 데이터들은 이미 정렬 되어있다고 가정하고 그 리스트에서 적절한 위치에 삽입이 되어지는 알고리즘이다.
• 데이터가 필요할 때만 위치를 바꾸므로 실행시간 면에서 효율적인 정렬 방식이다.
• 선택 정렬과 같이 동작원리를 직관적으로 이해하기 쉬운 알고리즘이다.

 

 

def insertion_sort(li):
    for i in range(1, len(li)):
        for j in range(i, 0, -1):  # 인덱스 i부터 1까지 감소하며 반복하는 문법
            if li[j] < li[j-1]:
                li[j], li[j-1] = li[j-1], li[j]
            else:
                break