정렬 알고리즘 : 삽입정렬

1. 삽입정렬 : 이해와 구현

삽입정렬이란 정렬대상을 두 부분으로 나눠서, 정렬 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 삽입해 가면서 정렬을 진행하는 알고리즘입니다. 그림을 통해 삽입정렬의 오름차순 정렬을 간단하게 보여드리겠습니다.

정렬 되지 않은 숫자 5 3 2 4 1 이 있다고 해봅시다. 그럼 일단 맨 좌측 값인 5가 정렬 되었다고 기준잡고 1번 인덱스부터 비교를 시작합니다. 1번 인덱스인 3이 더 작으므로 두 값을 스왑 해줍니다. 그럼 3,5,2,4,1 이렇게 변경이 됩니다. 여기 까지가 1단계입니다.

 

2단계는 2번 인덱스부터 비교를 시작합니다. 5와 비교했을 때 더 작으므로 5와 2 위치가 바뀌고 또 3과 비교했을 때 더 작으므로 3과 2의 위치가 바뀌어서 2단계는 2, 3, 5, 4, 1 이렇게 됩니다.

 

3단계와 4단계도 이와 마찬가지로 비교 대상을 시작으로 좌측으로 가면서 자기 자리에 맞게 끔 삽입되는 과정을 거칩니다. 이렇게 연산을 하여 최종적으로 정렬이 마무리 됩니다.

삽입 정렬은 자기 자리에 맞는 위치에 삽입되어 들어간다고 생각하시면 됩니다.

 

이해하기 쉽게 값이 삽입 되는 과정을 간단하게 설명 드리겠습니다

비교대상이 3일 때 3을 임시 버퍼에 저장하고 왼쪽으로 가면서 비교를 시작합니다. 임시버퍼에 저장된 값보다 큰 경우 오른쪽으로 한칸 씩 값을 이동합니다. 그리고 만약 임시버퍼보다 작은 값을 만나게 된다면 그 위치가 바로 임시버퍼의 값이 들어가는 자리입니다.

 

코드로 쫌 더 자세히 알아보겠습니다.

정렬대상은 인덱스 1부터 시작해서 마지막 인덱스인 4까지입니다. 따라서 바깥 쪽 for문의 범위는 i=1 ; i<size ; i++ 가 됩니다. 여기서 size는 배열의 크기입니다. 10번째 줄을 보면 정렬 대상을 insDate변수에 저장을 하게 됩니다. 안쪽 for문을 들어오게 되면 정렬 대상을 기준으로 왼쪽으로 비교를 해야합니다. 따라서 j의 시작 값은 i의 시작 값보다 1이 작아야 됩니다. 따라서 j=i-1 ; j>=0 ; j-- 의 조건이 나오게 된 것입니다.

 

그다음 아까 설명한 대로 정렬 대상과 비교를 시작합니다. 정렬 대상을 임시로 저장한 insData의 값과 비교를 하여 insData값이 더 작으면 현재 j 인덱스의 값을 오른쪽으로 미는 과정을 반복합니다. 계속 비교를 하다가 insData 값이 더 크게 되면 삽입 위치를 찾았단 소리이므로 else 문으로 들어와 break를 실행합니다.

 

그리고 안쪽 for문을 빠져 나옵니다. break 문으로 안쪽 for문을 빠져나온 경우 인덱스j의 값이 현재 정렬 대상의 값보다 더 작은 값을 뜻하므로 그다음 인덱스 j+1에 정렬 대상의 값이 들어가야 합니다. ary[j+1] = insData 이 부분입니다.

 

2. 삽입정렬 : 성능평가

정렬대상이 완전히 정렬된 상태라면, 안쪽 for문의 조건문은 항상 거짓이 되어 break문을 실행하게 됩니다.. 따라서 데이터의 이동도 발생하지 않고, 조건비교도 바깥쪽 for문의 반복횟수 이상 진행되지 않습니다.

 

하지만 최악의 경우를 고려하면 이 역시 앞서 보인 두 정렬 들 과 다를 바가 없습니다. 최악의 경우는 조건문이 항상 참이 되어 break문을 한 번도 실행하지 않는 경우입니다. 따라서 바깥쪽 for문의 반복 횟수와 안쪽 for문의 반복 횟수를 곱한 수만큼 비교 연산도, 이동 연산도 진행이 됩니다.

i가 4일 때 j는 4회의 비교 연산을 하게 되고 즉 size-1 만큼 연산을 하게 됩니다.

i가 3일 때는 j는 3회의 비교 연산을 하게 되고 즉 size-2 만큼 연산을 하게 됩니다.

따라서 size-1 + size-2 + ... + 2 + 1 = (size^2-size) / 2 의 값을 같게 됩니다.

따라서 빅-오는 O(size^2) 이 됩니다.

 

버블 정렬, 선택정렬, 삽입 정렬 모두 빅오는 O(n^2)으로 동일하지만 약간의 차이가 있습니다. 다음 시간에는 이 3가지 정렬의 성능에 대해서 비교해보는 시간을 가지겠습니다.