[06정렬] 6-3 삽입 정렬 (p161~p164)

[삽입 정렬]

• 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입.
• 즉, 삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬이라 함.
• 선택 정렬에 비해 구현 난이도는 높으나, 실행 시간 측면에서 더 효율적.
• 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적임.
• 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정.
• 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤 에, 그 위치에 삽입된다는 점이 특징임.

• 삽입정렬은 두 번째 데이터부터 시작한다. 첫 번째 데이터는 그 자체로 정렬되어있다고 판단하기 때문이다.

step0) 첫 번째 데이터 '7'은 그 자체로 정렬되어있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로 들어갈지 판단한다. '7'의 왼쪽으로 들어가거나 혹은 오른쪽으로 들어가는 두 경우만 존재한다. 우리는 카드를 오름차순으로 정렬하고자 하므로 '7'의 왼쪽에 삽입한다.

 

step1) 이어서 '9'가 어떤 위치에 들어갈지 판단한다. 삽입될 수 있는 위치는 총 3가지이며 현재 '9'는 '5'와 '7'보다 크기 때문에 원래 자리 그대로 둔다.

 

 step2) 이어서 '0'이 어떤 위치에 들어갈지 판단한다. '0'은 '5', '7', '9'와 비교했을 때 가장 적기 때문에 첫 번째 위치에 삽입한다.

 

step3) 이어서 '3'이 어떤 위치에 들어갈지 판단한다. '0'과 '5'사이에 삽입한다.

 

step7)

 

step8)

 

step9) 이와 같이 적절한 위치에 삽입하는 과정을 N-1번 반복하게 되면 다음과 같이 모든 데이터가 정렬된 것을 확인할 수 있다.

 

 

• 삽입 정렬은 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 특징이 있다.
• [step]을 보면 하늘색으로 칠해진 카드들은 어떤 단계든지 항상 정렬된 상태다.
• 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때, 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈춘다.

• [step 3]에서 '3'은 한 칸씩 왼쪽으로 이동하다가 자신보다 작은 '0'을 만났을 때 그 위치에 삽입됨.

 

[소스 코드]

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): #인덱스 i부터 1까지 감소하며 반복하는 문법
        if array[j] < array[j-1]: #한 칸씩 왼쪽으로 이동
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break #자기보다 작은 데이터를 만나면 그 위치에서 멈춤

print(array)

 

[삽입 정렬의 시간 복잡도]

• O(N^2)