삽입 정렬(Insertion Sort Algorithm)

삽입 정렬은 현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘이다.

 

1. 삽입 정렬은 두번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스 -1로 잡는다.

2. 별도로 저장해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다.

3. 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다.

4. 만약 삽입 변수가 더 크면, 비교 인덱스 +1에 삽입 변수를 저장한다.

 

이 정렬 알고리즘은 최악의 경우(역으로 정렬되어 있을 경우)엔 n-1개, n-2개... 1개씩 비교를 반복하여 시간복잡도는 O(N^2)이지만, 이미 정렬되어 있는 경우에는 한번씩밖에 비교를 하지않아 시간 복잡도는 O(N)이다.

하지만 상한을 기준으로 하는 Big-O notation은 최악의 경우를 기준으로 평가하므로 삽입 정렬의 시간복잡도는 O(N^2)이다.

 

공간복잡도는 단 하나의 배열에서만 진행하므로 O(N)이다.