삽입정렬

삽입정렬

삽입정렬은 이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 (i+1)개짜리 배열을 만드는 과정을 반복한다. 선택정렬과 버블정렬이 n개짜리 배열로부터 시작하여 그 크기를 하나씩 줄여나가는데 반하여, 삽입정렬은 1개짜리 배열로부터 시작하여 그 크기를 하나씩 늘려나가는 정렬이다.

insertionSort(A[], n) {

for i <- 2 to n {

loc <- i - 1;

newItem <- A[i];

while (loc >= 1 and newItem < A[loc]) {

A[loc + 1] <- A[loc];

loc--;

}

A[loc + 1] <- newItem;

}

}

삽입정렬은 최악의 경우에 수행 시간이 n(n-1)/2가 되고, 시간 복잡도가 O(n^2)가 된다. 최악의 경우가 아닌 일반적인 경우에는 수행 시간은 최악의 경우의 절반 정도가 되며, 시간 복잡도는 여전히 O(n^2)이다.

그러나, 배열이 기본적으로 어느정도 정렬이 되어 있을 경우에는 while문이 거의 실행되지 않게 되어 O(n)에 가까운 시간 복잡도를 갖게 된다.

선택 정렬과 버블정렬이 n개짜리 배열로부터 시작하여 그 크기를 하나씩 줄여나가는데 반하여, 삽입정렬은 1개짜리 배열로부터 시작하여 그 크기를 하나씩 늘려나가는 정렬이다. 좀더 정확히 말하면, 선택정렬과 버블정렬이 n개짜리 배열로부터 시작하여 아직 정렬되지 않은 배열의 크기를 하나씩 줄여나가는데 반하여, 삽입정렬은 1개짜리 배열로부터 시작하여 이미 정렬된 배열의 크기를 하나씩 늘려나가는 정렬이다.