삽입 정렬

삽입정렬이란 2번째 원소부터 n번째 원소까지 차례로 해당 원소가 위치할 인덱스에 원소를 삽입하는 방식을 사용하는 정렬 방식이다.

어떤 대상을 '오름차순'으로 정렬할 때 삽입정렬은 2번째 원소부터 앞의 원소와 비교하는 과정을 통해 적절한 위치에 삽입하고 n번째 원소까지 이 방식을 반복함으로써 정렬을 진행할 수 있다.

현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘이다.
'비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬'이기도 하다.
그리고 '안정 정렬'이다

삽입 정렬의 전체적인 과정은 이렇다. (오름차순을 기준으로 설명)

1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫 번째 타겟은 두 번째 원소부터 시작한다.)
2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다.
3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복한다.

첫번째 원소는 타겟이 되어도 비교할 원소가 없기 때문에 처음 원소부터 타켓이 될 필요가 없고 두 번째 원소부터 타켓이 되면 된다

[장정]
1. 추가적인 메모리 소비가 작다
2. 거의 정렬된 경우 매우 효율적이다. 즉 최선의 경우 O(N)의 시간복잡도를 갖는다
3. 안정정렬이 가능하다
[단점]
1. 역순에 가까울 수록 매우 비효율적이다. 즉, 최악의 경우 O(N²)의 시간 복잡도를 갖는다
2. 데이터의 상태에 따라서 성능 편차가 매우 크다

시간복잡도에 대해 잠깐 언급하자면, 위 알고리즘에서도 볼 수 있듯, 타겟 숫자가 이전 숫자보다 크기 전까지 반복하기 때문에 이미 정렬이 되어있는 경우 항상 타겟숫자가 이전 숫자보다 크다. 즉, 값을 N번만 비교하기 때문에 최선의 경우 O(N)의 시간 복잡도를 갖게 되는 것이다.

반대로 최악의 경우는 타겟 숫자가 이전 숫자보다 항상 작기 때문에 결국 N 번째 숫자에 대하여 N-1 번을 비교해야 한다. 그렇기 때문에 최악의 경우는 O(N2)의 시간복잡도를 보인다.

그럼 평균 시간 복잡도는? 이라는 질문이라면 삽입 정렬의 평균 시간 복잡도 또한 O(N2)의 시간 복잡도를 갖는다
결과적으로 최상의 경우와 최악의 경우의 평균으로 보더라도 '상한선'이라는 개념에 의해 O(N2)이 정설로 보고 있다.

물론 다음에 다룰 Bubble Sort나 Selection Sort 와 이론상 같은 시간복잡도를 갖음에도 평균 비교 횟수에 대한 기대값이 상대적으로 적기 때문에 평균 시간복잡도가 O(N2) 인 정렬 알고리즘 중에서는 빠른편에 속하는 알고리즘이다.
출처

public class 삽입정렬 {
    public static void main(String[] args) {
        // 배열 랜덤 생성
        int[] arr = new int[10];
        for(int i=0; i<10; i++){
            arr[i] = (int)(Math.random()*10);
        }
        // 2번째 원소부터 시작
        for(int i=1; i<arr.length; i++){
            // 현재 선택된 원소의 값을 임시 변수에 저장
            int index = arr[i];
            // 현재 원소 기준으로 이전 원소를 탐색하기위한 변수
            int temp = i-1;
            // 현재 원소가 이전 원소보다 크기 전까지 반복. 단 0번째 원소까지만 비교한다
            while(temp>=0 && index < arr[temp]){
                // 이전 원소는 한 칸씩 뒤로 미룬다
                arr[temp+1]=arr[temp];
                // 다음 대상 원소를 탐색한다
                temp--;
            }
            // 탐색이 종료된 지점에서 현재 선택되었던 변수의 값을 삽입해준다.
            // 여기서 탈출하는 경우 앞의 원소보다 index가 작다는 의미이므로
            // index는 temp뒤에 와야한다. 그러므로 index는 temp+1
            arr[temp+1]=index;
        }
        System.out.println(Arrays.toString(arr));
    }
}

참고링크