Insertion Sort(삽입 정렬)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.

Insertion Sort(삽입 정렬)

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

출처 : 위키 백과

예제

출처 : 위키 백과

의사 코드

Insertion Sort(A[], n) {    // 배열 A[1...n]을 정렬한다.
for i <- 2 to n {    ----------------------------------- ①
A[1...i]의 적당한 자리에 A[i]를 삽입한다.    ------- ②
}
}

수행시간 : 

① 의 for 루프는 n-1 번 반복

② 의 삽입은 최악의 경우 i-1 번 비교

최악의 경우 : T(n) = (n-1) + (n-2) + ... + 2 + 1 =  Θ(n²)

최선의 경우 : T(n) = n-1

시간복잡도 

n개의 데이터가 있을 때, 최악의 경우는   번 비교하게 되므로, 시간복잡도는 이 된다.

소스 코드(Java)