삽입정렬(Insertion Sort)의 개념 및 구현

삽입 정렬(Insertion Sort)

데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘이다.

삽입 정렬도 버블 정렬만큼 구현이 간단해서 프로그래머들에게 애용된다.

삽입 정렬은 아래와 같은 과정을 진행한다.(오름차순 정렬)

1. 데이터 집합에서 정렬 대상이 되는 요소들을 선택합니다. 이 정렬 대상은 왼쪽부터 선택해 나가며, 그 범위가 처음에는 2개지만, 알고리즘 반복 횟수가 늘어날 때마다 1개씩 커진다.
   정렬 대상의 최대 범위는 '데이터 집합의 크기 - 1' 이다.
2. 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 갖고 있는지 확인한다. 그렇지 않다면 이 요소를 정렬 대상에서 뽑아내고 이 요소가 위치할 적절한 곳을 정렬 대상 내에서 찾는다. 여기서 적절한 곳은 데이터 집합의 가장 왼쪽 기준으로 했을 때 자신보다 더 작은 요소가 없는 위치를 말한다.
3. 뽑아 든 요소를 삽입할 적절한 곳을 찾았다면, 정렬 대상 내에서 삽입할 값보다 큰 값을 갖는 모든 요소를 한 자리씩 오른쪽으로 이동시키고, 새로 생긴 빈자리에 삽입한다.
4. 모든 데이터 집합의 정렬이 완료될 때까지 1~ 3을 반복한다 

이를 토대로 그림 예시를 들어보겠다.

데이터 집합

먼저 정렬 대상을 선택해보자. 앞의 5, 1을 선택한 뒤 두 장 중 오른쪽이 왼쪽보다 큰지 비교한다.
1이 5보다 작기 때문에 1을 뽑아낸다. 1이 위치할 적절한 곳은 5의 왼쪽이기 때문에 5를 오른쪽으로 한 자리 옮긴다.

과정 1, 2를 진행한 모습

그러면 빈자리가 생겼기 때문에 해당 자리에 1이 들어간다.

과정 첫번째 반복 끝

이번엔 정렬 대상의 범위를 하나 더 늘려서 크기가 3개인 상태에서 과정 1부터 진행해야 한다.

이때 마지막 요소는 6인데 5과 비교했을 때 오름차순이 맞고 5 이전의 값은 이미 정렬이 되었기 때문에 다음 단계로 넘어간다.

다음 단계는 크기가 4개인 상태에서 가장 마지막 요소는 4인데 4는 6보다 작으므로 해당 요소를 뽑는다.

6보다 작기때문에 4 요소 pop

4가 위치할 곳은 왼쪽부터 순회했을 때 1 다음 이므로 5, 6을 오른쪽으로 옮긴다. 그런 다음 빈자리에 4를 삽입한다.

해당 과정이 끝난 모습

이런 과정을 앞으로 두 번 반복한다면 완전히 정렬된 데이터 집합이 될 것이다.

아래는 삽입 정렬이 대략 어떻게 진행되는지 한눈에 알 수 있는 유튜브 영상이다.

버블 정렬은 정렬 대상을 줄여나가던 반면에 삽입 정렬은 정렬 대상을 하나씩 늘려 나가는 방식을 이용한다. 그럼 성능에 대해 알아보겠다.

삽입 정렬은 버블 정렬보다 빠를까?

예제에서 데이터 집합의 크기는 6인데 정렬은 5번 수행된다. 비교는 정렬 대상의 범위가 2일 때 1번, 3일 때 2번... 6일 때 5번 수행된다. 이로부터 삽입 정렬의 비교 횟수를 계산하면 아래와 같다

삽입 정렬의 비교 횟수 = 1 + 2 +... + (n - 2) + (n - 1)
=$$\frac{n + (n - 1)}{2}$$ 

버블 정렬과 비교 횟수가 같지만 분명한 차이가 존재한다. 위 예제에서 [1, 5, 6 ,4]를 정렬할 때 3번의 비교하는 것이 아닌 2번을 비교했다. 이는 1은 정렬된 상태기 때문에 5, 6만 비교를 했다.

그래서 삽입 정렬에는 데이터가 정렬되어 있는 경우와 그렇지 않은 경우가 존재한다. 이것들의 비교 횟수의 평균을 낸다면

=$$\frac{\frac{n(n-1)}{2} + (n - 1)}{2}$$ 
=$$\frac{n^{2} + n - 2}{2}$$ 

결국 성능은 삽입 정렬이 좀 더 낫다는 것을 알 수 있다. 따라서 비교적 크기가 작은 데이터 집합을 정렬할 때는 버블 대신 삽입 정렬을 사용한다.

위 내용을 정리하자면 삽입 정렬의 시간 복잡도는 최고와 최악이 존재하며 최고일 때는 O(n) , 최악일 때는 O(n²) 

공간 복잡도는 버블 정렬처럼 배열 하나만 이용하기 때문에 O(n)

삽입 정렬 구현

int[] sort()
{
    for(int i = 1; i < array.length; i++)
    {
        if(array[i - 1] <= array[i])
            continue;

        int target = array[i];
        int j = i;

        while (j > 0 && array[j - 1] > target)
        {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = target;

    }
    return array;
}

우선 정렬 범위를 정한 뒤 대상을 찾아야 하는데 현재 요소와 이전 요소를 비교해 이전 요소가 더 크다면 현재 요소를 정렬 대상으로 정한다.

다음 정해둔 범위에서 타깃 앞에서부터 역순으로 순회하는 요소와 타깃 요소를 비교한다. 만약 타겟보다 크다면 순회요소를 오른쪽으로 한 칸 옮긴다.

순회가 끝난다면 타겟요소 들어갈 적절한 위치를 찾은 것이므로 해당 위치에 타깃 값을 대입한다.

정리

• 장점 : 버블 정렬보다 빠르다, 데이터가 정렬되어있다면 정렬이 빠르다
• 단점 : 버블 정렬과 동일하게 데이터가 많다면 오래 걸린다.