55. Insertion Sort (삽입 정렬) 파헤치기

Insertion Sort(삽입 정렬)이란 비효율 정렬(O(n^2))이지만, 한 가지 특징으로 인해 알아둘 필요가 있다.

흔히 비효율 정렬에는 대표적으로 3개가 있는데 바로 

'Bubble Sort(버블 정렬)', 'Selection Sort(선택 정렬)', 'Insertion Sort(삽입 정렬)'이다.

이 중에서 선택 정렬은 버블 정렬보다 완벽히 상위 호환이므로, 버블 정렬을 정렬 알고리즘 분류에서 빼야 한다는 말도 있다.

선택 정렬의 알고리즘은 무척 간단하다.

각 단계별로 최소값 또는 최대값을 찾아 정렬하고 있는 위치에 저장한다.

이전에 비교 방식에서 최소값 또는 최대값을 찾는데 쓰이는 비교 회수는 n-1, n-2, n-3, ... 1번이다.

그리고 이의 -1 등차수열의 합이 바로 선택 정렬의 총 비교 회수이다.

선택 정렬은 모든 정렬 알고리즘 중에서 가장 기초이다. 딱히 특별한 성질은 없고, 하나씩 찾아나가면서 정렬하는 방식이다.

그리고 이런 선택 정렬과 더불어 또 다른 비효율 정렬이 바로 삽입 정렬이다.

삽입 정렬은 비효율 정렬이지만 특정 경우에 한해서는 무척이나 빠르다.

그 특정 경우란 한 마디로 이미 정렬되어 있는 경우(0으로 채워진 제로 배열 포함)를 말한다.

선택 정렬이 배열의 요소를 중복해서 계속 비교해나가는 알고리즘이라고 한다면,

삽입 정렬은 길이 1에서부터 길이 N까지 늘려가며 자신의 자리를 찾아가며 정렬해나가는 방식이다.

이 때, 각 길이별로 정렬이 되어있어야 한다.

요약하면 다음 두 가지의 과정의 반복으로 삽입 정렬은 이루어진다.

(1) 원소를 하나 추가.

(2) 추가된 원소를 적절한 위치에 삽입.

즉, 5 2 1이라는 배열이 있을 때,

맨 처음에 길이 1에서 정렬된 배열은 

5 (완료)

다음 길이 2에서 정렬된 배열은

5 2

(자기위치 찾기)

2 5 (완료)

다음 길이 3에서 정렬된 배열은

2 5 1

(자기위치 찾기)

1 2 5 (완료)

즉, 이전 시행의 결과로 인해 현재 검사 대상까지의 배열이 정렬되어 있다는 것이 중요하다.

이 성질로 인해 삽입 정렬은 독특한 특징을 가지는데, 

현재 검사 대상이 이전 요소보다 크다면, 그 때의 비교 수행을 하지 않고 다음 단계로 진행된다.

예를들어)

만약 1 2 5 라는 배열이 있으면, 

첫 단계

1

두 번째 단계

1 2 (비교 수행 안함)

세 번째 단계

1 2 5 (비교 수행 안함)

그렇기에 이미 정렬된 배열이라면, 각 시행은 Constant 시간에 끝이 난다.

이 성질을 이용해 이 배열이 정렬된 배열인지 검사하거나, 어느정도 정렬된 배열을 정렬하는데 유용하게 쓰인다.

다음은 여러가지 방식의 삽입 정렬 코드이다.

결국 모든 방식은 똑같지만 표현만 다르다. - 각자 이해하기 편한대로 이해하면 좋다.

(1) SWAP 방식

(2) 뒤로 미루기 방식

(3) 아마존 SW 수석 Developer 방식

(4) 서울대 저자 방식

(5) 서울대 저자 방식 2

(6) 서울대 저자 방식 (함수 호출 x)

(*) 출력 - 제로 배열 수행했을 때

이미 정렬된 배열을 6가지 방식으로 수행하였을 때, 나온 결과이다.

이때 0.02초에 수렴하는 방식들은 함수 콜이 존재하므로 발생한 시간이다.

함수 콜을 사용하지 않는 방식은 모두 0.005초 안에 끝이 났다.

삽입 정렬의 기초부터 그 원리까지 하나씩 다 파악했다. 이젠 절대 잊어버리지 말자.