삽입 정렬 Insertion Sort

정의

오름차순으로 정렬하는 기초적인 알고리즘 중 하나

기법

무차별 대입 Brute Force

알고리즘 순서

1. 첫번쨰부터 마지막 까지 순회한다
2. 순회하는 수와 왼쪽에 있는 수를 비교한다.
3. 만약에 왼쪽의 수가 오른쪽 보다 크다면 작은수를 왼쪽 큰수를 오른쪽에 넣는다
4. 앞에서 비교되었으니 왼쪽을 한번더 비교 하여 작은수를 왼쪽 큰수를 오른쪽에 넣는다
5. 왼쪽의 수가 오른쪽 보다 크지 않다면 더이상 비교할 필요가 없다
6. 마지막 까지 반복한다.

자바 코드

    public static int[] insertSort(int[] input) {
        for (int i = 1; i < input.length; ++i) {
            int chkPos = i;
            while (chkPos > 0) {
                if (input[chkPos - 1] > input[chkPos]) {
                    int temp = input[chkPos];
                    input[chkPos] = input[chkPos - 1];
                    input[chkPos - 1] = temp;
                }
                --chkPos;
            }
        }
        return input;
    }

평균 시간 복잡도 Avg. time complexity

$O(n^2)$

최악 시간 복잡도 Worst time complexity

$O(n^2)$

공간 복잡도 space complexity

$O(1)$

안정성 stability

yes

계산법

순회 횟수

$n$

가장 많이 방문한 요소 수

$n$ (첫번째 요소)

가장 적게 방문한 요소 수

$1$ (마지막 요소)

평균적으로 방문한 요소 수

(가장 많이 방문한 요소 수+가장 적게 방문한 요소)/2 $= \frac{(n+1)}{2}$

다항식 시간

순회 횟수*평균적으로 방문한 요소 수 $=n\cdot \frac{n+1}{2}=(\frac{n^2}{2}+\frac{n}{2})$

시간 복잡도

$O(다항식 시간)=O((\frac{n^2}{2}+\frac{n}{2}))=O(n^2)$