[lecture] 6주차.정렬 알고리즘_삽입 정렬

수업을 듣고 정리한 내용입니다.

삽입 정렬(Insertion Sort)

삽입 정렬이란, 배열을 정렬된 부분(앞 부분)과 정렬이 안된 부분(뒷 부분)으로 나누고, 정렬 안된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복하여 진행하는 정렬이다.

위와 같은 배열이 있다고 가정하였을 때, 삽입 정렬을 실행하면 아래와 같다.

정렬이 안된 부분의 숫자 하나가 정렬된 부분에 삽입됨으로서, 정렬된 부분의 원소 수가 1개 증가하는 동시에 정렬 안된 부분의 원소 수는 1개 감소한다. 이것을 반복해 수행하면, 마지막엔 정렬아된 부분엔 아무 원소도 남지 않고, 입력이 정렬된다. 정렬은 배열의 첫 번째 우너소만이 정렬된 부분에 있는 상태에서 정렬을 시작하게 된다.

//Insertion Sort
입력 : 크기가 n인 배열 A
출력 : 정렬된 배열 A
for i=1 to n-1
	CurrentElement = A[i]	//
    j <- i-1
    while (j >= 0

시간복잡도

for 루프가 (n-1)회 수행하기 때문에 이때 1 + 2 + ... + (n-2) + (n-1) = n(n-1) / 2이고, 루프 내부는 O(1) 시간이므로 총 n(n-1) / 2 * ㅒ(1) = O(n^2)이다.

입력이 이미 정렬되어 있다면, 항상 각각 CurrentElement가 자신의 왼쪽 원소와 비교한 후 자리이동 없이 원래 자리에 위치하고, while-루프 조건이 항상 False 이므로 원소의 이동도 전혀 없다. 따라서 (n-1) 번의 비교만에 정렬을 마치게 된다. 이 때 최선 시간 복잡도 값은 O(n)이다.

평균 시간 복잡도는 CurrentElement가 자신의 자리를 포함해 앞부분의 각 원소에 자리잡을 확률이 같다고 가정하기 때문에 O(n^2 / 4) = O(n^2)이다.

삽입 정렬의 특성

1. 거의 정렬된 상태에서는 가장 빠르게 정렬한다.

2. 입력의 크기가 작을 때 가장 성능이 좋다.

3. 퀵 정렬과 합병 정렬에서 입력의 크기가 작아진 경우 순환호출을 중단한 후 삽입 정렬을 사용한다.

4. Tim Sort에서 입력의 크기가 64이하인 경우 순환호출을 중단한 후 삽입 정렬을 사용한다.