[정렬] - 삽입정렬

 

삽입정렬

- 처리되지 않은 특정한 데이터를 하나씩 골라 적절한 위치에 삽입

- 선택 정렬보다 실행 시간이 조금 더 효율적이다

- 특히, 데이터가 정렬 되어 있을 때 더욱 효과적이다.

(선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교한다)

- 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞의 데이터들은 이미 정렬되어 있다고 가정한다

- 정렬되어 있는 앞쪽의 데이터 리스트에서 적절한 위치를 찾은 후, 그 위치에 삽입

 

 

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

 

 

STEP 0)  5가 들어갈 수 있는 위치는 앞 쪽의 데이터인 7의 왼쪽이나 오른쪽, 총 2가지 경우만 존재한다.

우리는 카드를 오름차순으로 정렬할 것이기 때문에 7의 왼쪽에 삽입한다 

 

 

 

 

STEP 2) 이어서 9가 어느 위치에 들어갈지 판단한다. 삽입될 수 있는 위치는 위의 그림처럼 3가지이며 9는 앞의 정렬된 데이터인 5와 7보다 크기 때문에 맨 오른쪽에 위치하는데 이는 원래 자리이므로 그대로 둔다.

 

STEP 8)  위와 같은 과정을 반복 후 나온 결과

 

STEP 9) 앞의 방법을 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): 
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

 

삽입 정렬의 시간 복잡도

-  선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되어 O(N^2)

- 하지만 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 조금 더 빠르게 동작( 최선의 경우 O(N))

- 가장 주로 사용하는 퀵정렬 보다 삽입정렬이 비효율적이나 거의 정렬되 있는 상황에서는 퀵정렬 보다 더 빠르다