삽입정렬

Chapter. 1

1. 삽입 정렬

삽입정렬을 배우면서 최악의 경우가 아닌 다른 시나리오를 분석하는 것에 어떤 장점이 있는지 알아보자.

2. 예제

배열 [4,2,7,1,3]을 삽입 정렬 해보자.

준비: 인덱스 1의 값을 확인하며 첫번째 패스스루를 시작하겠다. 인덱스 1에 값에 2가 들어있다. 임시로 2를 삭제하고 변수에 저장한다.
1. 4 변수에 있는 2를 비교한다.
2. 4가 2보다 크므로 4를 오른쪽으로 시프트한다. 공백이 배열의 왼쪽 끝에 있으므로 더이상 왼쪽으로 시프트할 수 없다.
3. 변수를 다시 배열에 삽입해서 첫 번째 패스스루를 끝낸다.
준비: 두번째 패스스루를 시작한다. 두번째 패스스루에서는 인덱스 2의 값을 임시로 삭제한다. 이 값을 변수에 저장한다.
4. 4와 변수 값을 비교한다. 4가 더 작으므로 시프트 하지 않는다. 변수보다 작은 값에 도달했으므로 시프트 단게를 끝낸다.
5. 변수를 다시 공백에 삽입하고 두 번째 패스스루를 끝낸다.
.
.
.
18. 변수를 다시 공백에 삽입한다. 이제 배열이 완전히 정렬됐다.

3. 삽입정렬 구현

def insertion_sort(array):
	
    # 인덱스 1부터 시작해 전체 배열을 순화하는 루프를 시작시킨다. 현재의 인덱스를 index	변수에 저장한다.
	for index in range(1, len(array)):
  	 	# 현재 index가 무엇이든 인덱스를 position에 할당한다. 인덱스에 있는 값도 temp_value 변수에 할당한다. 
    	position = index
        temp_value =arrary[index]
        
        # while 루프를 시작한다. position 안쪽에 있는 값이 temp_value보다 큰지 확인한다. 크다면 왼쪽값을 한 셀 오른쪽으로 옮긴 후 position 값을 1감소시킨다. 이어서 새 position의 왼쪽 값이 temp_value보다 큰지 확인하고 temp_value보다 작은 값을 찾을 때 까지 이 과정을 반복한다.
        while position > 0 and array[position - 1] > temp_value:
        	array[position] = array[position] - 1
            position = position - 1 
            
        # temp_value를 배열의 공백에 삽입힌다.
        array[position] = temp_value     

효율성

삽입정렬에 포함된 단계는 삭제, 비교, 시프트, 삽입, 네 종류다. 삽입 정렬의 효율성을 분석하려면 각 단계별 총합을 게산해야한다. 비교의 경우 대략 $N^2/2$번의 비교가 일어난다. 시프트는 비교횟수만큼 시프트가 일어난다. 삽입과 삭제는 패스스루 당 한 번 일어난다. $N-1$번 이므로 $N-1$번의 삭제와 N-1의 삽입이 있을 것이다.

비교와 시프트를 합쳐서 $N^2$번 삭제 $N-1$번 삽입 $N-1$을 합치면 $N^2 + 2N-2$단계이다.

빅오는 상수를 무시한다는 규칙에 따라 $O(N^2+N)$으로 단순화시킬 수 있다. 빅오 표기법은 가장 높은 차수의 N만 고려한다. 결국 $O(N^2)$이 된다.

삽입정렬과 버블정렬, 선택정렬은 모두 O(N^2)이다.

평균적인 경우?

최악의 시나리오에서는 선택 정렬이 삽입 정렬보다 빠른 게 사실이다. 하지만 평균 시나리오도 중요하게 고려해야 한다.
삽입 정렬이 최악의 시나리오에서 $N^2$가 걸린다면 평균 시나리오에서는 $N^2/2$ 단계가 걸린다. 하지만 빅오 관점에서는 두 시나리오 모두 O(N^2)이다.

최선의 평균, 최악의 시나리오를 구분하는 능력은 기존 알고리즘을 최적화 해서 훨씬 빠르게 만드는 것만큼이나 사용자 요구에 맞는 최적의 알고리즘을 고르는 핵심 기술이다.

마치며

이 포스트는 도서 누구나 자료 구조와 알고리즘을 읽고 정리한 내용을 작성한 글입니다.