Sorting Algorithms - 삽입 정렬(Insertion Sort)

Park Suyong·2020년 9월 2일
0

개인 알고리즘

목록 보기
3/19

1. 정의

삽입 정렬(Insertion Sort)에 대해서 알아보도록 한다.

삽입 정렬이란 배열의 2번째 요소부터 검사를 시작하여 비교 대상인 요소와 대소 관계를 따진 후, 요소를 이동하는 것을 말한다.

2. 방식

예를 들어, 아래의 모습을 한 배열이 있다고 가정하자.

첫 번째 시작 대상은 2번째 요소인 4부터 시작한다. 이 때 4는 6보다 앞에 위치해야 하므로 4를 6의 앞에 삽입한다.
[6, 4, 1, 7, 3, 9, 8]

아래의 배열은 4를 6앞에 삽입하고 6을 오른쪽으로 밀어낸 상태가 된다. 이 때 다음으로 1이 4나 6보다 앞에 있어야 하므로 1을 4앞에 삽입하도록 한다.
[4, 6, 1, 7, 3, 9, 8]

아래의 배열은 1을 4앞에 삽입하고 4부터 오른쪽으로 밀어낸 상태가 된다.
[1, 4, 6, 7, 3, 9, 8]

위와 같은 작업을 반복적으로 취하게 되면 정렬은 완료되게 된다. 즉, 정렬이 완료된 부분(왼쪽)과 정렬이 완료되지 않은 부분(오른쪽)의 첫 번째 요소를 알맞은 위치에 삽입하는 것이 삽입 정렬이 되는 것이다.


그런데 이 때, 알맞은 위치에 어떻게 삽입하느냐가 관건이 될 것이다. 먼저, 0번째 인덱스는 이미 정렬되어 있다고 가정한다. Outer Loop는 따라서 배열의 1번째 요소부터 시작하게 된다. 현재 요소(배열의 1번째 요소)를 임시 변수에 저장한 후 Inner Loop의 조건에서 0번째 인덱스와의 크기를 비교한다. 이를 통해, 정렬된 배열이 지속적으로 생기고 커져나간다는 것을 알 수 있다.


3. 구현

이와 같은 작업을 코드로 구현하여 보자.

public class Main {
 
    public static void main(String[] args) {
        int[] array = {22, 5, 11, 32, 120, 58, 70, 6, 8};
        Insertion_Sort(array);
    }
 
    public static void Insertion_Sort(int[] arr) {
 
        int temp, j;
        for(int i = 1; i < arr.length; i++) {
            temp = arr[i];
            for(j = i - 1; j >= 0 && arr[j] > temp; j--)
                arr[j + 1] = arr[j];
            arr[j + 1] = temp;
        }
 
        for(int k : arr) System.out.println(k + "");
    }
}

4. 결론

삽입 정렬은 처음부터 그 개념을 이해하기가 쉽지 않았다. 2 ~ 3번 반복해서 보니 이해가 됐다.
코드에서 arr[j + 1] = temp 이 부분을 이해하려고 하는데 애먹었던 것 같다. 더 열심히 하자.

삽입 정렬은 최선의 경우 O(n) 이라는 엄청나게 빠른 속도를 가진다. 따라서 현재에도 다른 정렬 알고리즘의 일부로 사용되기도 한다. 하지만 최악의 경우 O(n²) 이라는 시간복잡도를 갖게 된다.

이상 삽입 정렬을 구현해 보았다.

profile
Android Developer

0개의 댓글