[알고리즘][정렬] - 삽입 정렬

삽입 정렬이란?

데이터들을 기존의 배열과 비교하여

자신의 위치를 찾아 삽입하여 정렬을 완성하는 알고리즘

 

삽입 정렬 예시

오름차순으로 정렬된 [1, 2, 3, 4, 5, 6, 8, 9]

배열이 존재한다고 가정하고 7 이라는

새로운 데이터가 주어졌을 경우

앞(뒤)에서부터 비교하여 6 과 8 사이에 삽입

뒤에서부터 비교하는 삽입 정렬 예시

int[] preSortedArray = {1, 2, 3, 4, 5, 6, 8, 9}; 
int preSortedArrayLength = preSortedArray.length;
int newData = 7; 
int placeInArray;
// 크기 증가가 안되는 배열의 특성을 고려하여 새로운 배열 생성
int[] newArray = new int[preSortedArrayLength + 1]; 

// 뒤에서부터 비교
for (placeInArray = preSortedArrayLength - 1; placeInArray >= 0; placeInArray--) {
    if (preSortedArray[placeInArray] > newData) { // 앞으로 이동해서 비교를 이어나가는 경우
        // newData 가 본인보다 앞에 삽입될 예정이므로 뒤로 한 칸 이동
        newArray[placeInArray + 1] = preSortedArray[placeInArray];
    } else { // 삽입할 위치를 찾은 경우
        break;
    }
}

// break 한 위치에 삽입
newArray[placeInArray + 1] = newData; 

// 새로운 데이터가 삽입된 부분의 앞의 요소들 복제(영향을 받지 않는 인덱스들)
for (int i = 0; i <= placeInArray; i++) { 
    newArray[i] = preSortedArray[i];
}

 

 

 주의점

거의 정렬이 완료된 배열에 대해서는 매우 효율적이고 안정적이나

데이터 요소의 개수가 많은 경우 심각한 성능 저하 문제 발생

 

따라서 데이터의 규모가 비교적 작은 상황에서 적절하다

또한 배열 내의 요소들이 자리를 바꾸게 되는 과정에서

원본 데이터가 수정되므로 주의가 필요하다

(삽입 정렬의 단점을 보완한 쉘 정렬에 대한 설명 보러 가기)

 

 

 

정렬된 배열을 사용할 경우: O(n)

 정렬되지 않은 배열을 사용할 경우: O(n^2)

∴  O(n^2) 의 시간 복잡도를 가진다