삽입 정렬

 

삽입정렬

 

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
• 데이터를 하나씩 확인하면서, 이 데이터는 어느 위치에 들어가는게 맞을 지 매번 계산해서 적절한 위치에 들어갈 수 있도록 해줌
• 선택 정렬에 비해 구현 난이도가 높지만, 더 빠르게 동작
• 앞쪽에 있는 원소들이 이미 정렬되어있다고 가정하고, 뒤 쪽에 있는 원소를 앞 쪽에 있는 원소의 위치 중에서 한 곳으로 들어가도록 만드는 방식으로 동작

 

처음 시작 시, 첫 번째 원소는 그 자체로 정렬되어 있다고 판단하고 두 번째 데이터가 어떤 위치로 들어갈지 판단.

카드 게임을 할 때, 새로운 카드가 들어오면 새로운 카드를 기존 정렬된 카드 사이 올바른 자리를 찾아 삽입함으로써 정렬이 유지되도록 하는 것과 같음.

 

삽입 정렬 예시

 

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)):
    for j in range(i, 0, -1): # j는 삽입하고자 하는 원소의 위치. 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

 

 

 

• 시간복잡도: O(N^2), 선택정렬과 마찬가지로 반복문이 두번 중첩.
• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작.
• 최선의 경우 O(N)의 시간복잡도.