삽입 정렬(insertion sort)

이전의 포스팅에서 버블 정렬과 선택 정렬을 알아보았는데, 둘 다 효율성은 O(N2)이지만 선택 정렬이 실제로는 두배 더 빠르다는 것을 알 수 있었다. 이번에는 삽입 정렬(insertion sort)을 배우면서 최악의 경우가 아닌 다른 시나리오를 분석하는 것에 중점을 두고 어떠한 장점이 있는지 알아 보겠다.

 

삽입 정렬의 수행 순서

 

삽입 정렬을 수행 할 배열은 [2, 4, 7, 1, 3] 이다.

 

먼저 loop1이다.

 

 

1. 먼저 인덱스 1의 값을 확인한다.
2. 임시로 인덱스1(값2)를 삭제한 후 temp_value 변수에 저장한다
3. 인덱스 - 1(값4)와 비교한다.
4. 4가 2보다 크므로 4를 오른쪽으로 쉬프트 한다.
5. 더이상 비교할 인덱스가 없으므로 temp_value를 -1인덱스에 삽입한다.

 

첫번쨰 루프의 결과는 [2, 4, 7, 1, 3] 이다.

 

 

다음은 loop2이다.

 

 

1. 인덱스 2의 값을 삭제 한후 temp_value에 저장한다.
2. 인덱스 1과 비교 한다.
3. 인덱스 값 4와 비교하였을때 더 크므로 더이상 시프트 하지 않고 그대로 삽입한다.

 

 

두번쨰 루프의 결과는 [2, 4, 7, 1, 3] 이다.

 

이러한 과정을 모두 거치면 비로소 정렬이 완료된다.

 

세번째 루프

 

네번째 루프

 

삽입 정렬 구현

 

파이썬으로 삽입 정렬을 구현 하였다.

 

def insertionSort(array):
    
    for index in len(1,array): #array 길이만큼
        
        temp_value = array[index] # 바꿀값을 빼낸다.       
        position = index-1 # 바꿀값의 위치


        # 한번의 스루패스
        while position >=0: # positon 이 0이 될 때 까지

            if( array[position] > temp_value ): # 바꿀값이 위치보다 작다
                
                array[position + 1] = array[position] # 포지션의 위치를 오른쪽으로 쉬프트
                position = position -1 # 다음 포지션을 비교

            else:
                
                break # 포지션보다 바꿀값이 더작다. 

        array[position + 1] = temp_value # 비교할 포지션의 조건이 만족하지 않기에 오른쪽에 삽입
    
    return array

 

삽입 정렬의 효율성

 

• 비교 : N-1
• 삭제 : N-1
• 삽입 : N-1
• 상수를 무시하고 단순화 시켰을떄 효율성: O(N2 + N)

 

평균적인 경우의 효율성

 

최악의 시나리오에서는 선택 정렬이 삽입 정렬보다 빠른게 사실이지만 평균시나리오도 중요하게 고려해야 한다.

정의에 따르면 가장 자주 일어나는 경우가 평균 시나리오 이며 최선의 그리고 최악의 시나리오는 드물게 발생한다. 값이 완벽히 오름차순 또는 내림차순으로 정렬된 경우는 극히 드물다.

 

배열이 역순으로 정렬된 최악의 시나리오에서 각 패스스루마다 비교하고 시프트 한다(N2번의 비교와 시프트)

하지만 이미 오름차순으로 정렬된 최선의 시나리오는 패스스루당 한번의 비교만 하며 시프트는 일어나지 않는다.(N-1번의 비교)

 

어떤 패스스루에서는 temp_value 왼쪽의 모든 데이터를 비교하는 반면 보다 작은값을 만나면서 일찍 종료 되기 된다. 이러한 경우는 평균 시나리오에서 예를 들 수 있는데 대체적으로 데이터의 반을 비교하고 시프트 할 것이다. (N2 / 2(빅 오의 관점에서는 모두 O(N2)))

 

선택 정렬과 삽입 정렬의 비교

 

	최선의 시나리오	평균 시나리오	최악의 시나리오
선택 정렬	N2 / 2	N2 / 2	N2 / 2
삽입 정렬	N	N2 / 2	N2

 

평균적인 경우라면 두 정렬모두 유사하게 수행 되지만 앞서 말했듯이 따져보면 거의 정렬된 데이터라고 가정 하면 삽입 정렬이 훨씬 효율적이라고 볼 수 있다.

 

---

 

세 시나리오를 구분하는 능력은 알고리즘을 최적화해 훨씬 효율성을 좋게 만드는 것 만큼이나 사용자 요구에 맞는 최적의 알고리즘을 고르는 것이 핵심 기술이다. 최악의 경우를 대비하는 것도 좋지만 대부분은 평균적인 경우가 일어난다는 점을 명심 해야겠다.