삽입 정렬(Insertion Sort)

- 삽입 정렬은 해당 작업을 반복한다

1. 차례대로 값을 지정한다(첫 번째 생략)

2. 정렬될 위치를 찾는다(한 칸씩 앞으로 이동)

3. 해당 순서에 넣기 위해 자리를 만든다(한 칸씩 뒤로 이동)

(교환이 없다면 이미 정렬이 되어있는 상태) 

 

선택 정렬과 작동이 비슷한 느낌의 방법

그보다 효율적이지만 구현이 비교적 복잡하고 직관적이지 못하다

추가로 더 빠르고 좋은 정렬 알고리즘이 많이 나와있어서

이 정렬을 굳이 사용해보겠다가 아니라면 잘 안쓰지 않을까

버블이나 선택 정렬은 만들기라도 쉬우니 귀찮다면 쓸거같은데...

 

 

- 자바로 간단한 예제를 짜고 주석을 달아놓고

//n개 입력 값을 받음(입력 값을 모른다는 가정)
int[] array = new int[n];

//정렬 중인 값
int key;
//비교를 위한 번호
int compareIdx;

//정렬을 위한 입력 값 순환
for(int sortIdx = 1; sortIdx < array.length; sortIdx++) {
    key = array[sortIdx];
    compareIdx = sortIdx - 1;

    //삽입을 위한 입력 값 순환
    while(compareIdx >= 0 && array[compareIdx] > key) {
        //한 칸씩 뒤로 이동
        array[compareIdx + 1] = array[compareIdx];
        compareIdx--;
    }

    //삽입할 위치에 값 삽입
    array[compareIdx + 1] = key;
}

//결과 출력
System.out.println(Arrays.toString(array));

 

 

- 마지막으로 시간 복잡도(Big-O)에 대해 말하자면

외부 반복문은

배열 첫 번째 방을 제외한 n-1 실행

여기서 상수는 무시함으로

n-1

-> O(n)

 

내부 반복문을 계산 할 경우

매 반복마다 정렬된 방을 제외로

기존 중첩 반복문으로 정확한 계산이 불가하다

ex) O(n) * O(n) = O(n^2)

 

하지만 전체 횟수를 등차수열의 합으로 표현할 수 있으며

ex) 1 + 2 + ... + (n - 2) + (n - 1)

 

예를 들어 배열이 다섯개가 주어진 경우

(5 - 4) + (5 - 3) + (5 - 2) + (5 - 1) = 10

 

여기서 등차수열의 합 공식을 풀이하고

항의 개수 / 2 * (첫 번째 값 + 마지막 값)

-> n - 1 / 2 * (1 + (n - 1))

-> n - 1 / 2 * (1 - 1 + n)

-> n - 1 / 2 * n

-> n(n - 1) / 2

 

등차수열의 합으로 계산을 한다면

5(5 - 1) / 2

-> 20 / 2

-> 10

 

다음 빅오 표기법을 적용하면

1. 상수 계수 무시(분모 포함)

2. 가장 큰 차수만 남김

n(n - 1) / 2

-> n^2 / 2 - n / 2

-> O(n^2)

 

마지막으로 외부 반복문과 내부 반복문을 합하지만

여태까지 말했던 상수와 작은 차수를 제외하면

O(n) + O(n^2)

-> O(n^2)

 

특이 사항으로 최선(최적) 예를 들어 이미 정렬이 돼있다면

O(n)을 가지지만 시간 복잡도는 최악인 경우를 상정하여

 

선택 정렬은 O(n^2)의 시간 복잡도를 가진다