Insertion Sort (삽입 정렬)

삽입 정렬(Insertion Sort)은 정렬 알고리즘 중 하나로, 손 안의 카드를 정렬하는 방법과 유사하다. 새로운 카드를 기존의 정렬된 카드 사이에 올바른 자리를 찾아 삽입하는 방식이다. 이는 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

로직

1. 기준 원소 선택: 두 번째 위치(index)부터 탐색을 시작하여 현재 위치의 값을 standard에 저장한다.
2. 비교 및 이동: standard와 이전 원소들을 비교하여, standard가 삽입될 위치를 찾는다. 이 과정에서 standard보다 큰 원소들은 오른쪽으로 한 칸씩 이동한다.
   3.삽입: 삽입할 위치를 찾으면 standard를 그 위치에 삽입한다.
   4.반복: 다음 위치로 이동하여 이 과정을 반복한다.

예제 코드

public class InsertionSort {
    public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) { // 1
            int standard = arr[i];
            int index = i - 1;

            while ((0 <= index) && standard < arr[index]) { // 2
                arr[index + 1] = arr[index];
                index--;
            }
            arr[index + 1] = standard; // 3

            print(arr, i);
        }
    }

    private static void print(int[] arr, int step) {
        System.out.print(step + "단계 : ");
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {6, 7, 2, 4, 3, 9, 1};
        sort(arr);
    }
}

단계별 결과

1단계 : 6 7 2 4 3 9 1 
2단계 : 2 6 7 4 3 9 1 
3단계 : 2 4 6 7 3 9 1 
4단계 : 2 3 4 6 7 9 1 
5단계 : 2 3 4 6 7 9 1 
6단계 : 1 2 3 4 6 7 9

시간 복잡도

삽입 정렬의 시간 복잡도는 다음과 같다:

• 최악의 경우: O(N^2) - 모든 원소가 역순으로 정렬된 경우.
• 최선의 경우: O(N) - 배열이 이미 정렬된 경우.
• 평균의 경우: O(N^2) - 일반적인 경우.

삽입 정렬은 대부분의 원소가 이미 정렬되어 있는 경우 매우 효율적이다. 최악의 경우, 선택 정렬과 동일하게 (n-1)+(n-2)+...+2+1이므로 O(N^2)이다. 하지만 이미 정렬된 배열의 경우, 한번씩만 비교하므로 O(N)의 시간 복잡도를 가진다.

공간 복잡도

삽입 정렬은 주어진 배열 안에서 교환을 통해 정렬이 이루어지기 때문에 추가적인 메모리 공간이 필요하지 않다. 따라서 공간 복잡도는 O(1)이다.

장점

• 알고리즘이 단순하고 구현이 쉽다.
• 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
• 선택 정렬이나 버블 정렬에 비하여 상대적으로 빠르다.
• 안정 정렬이므로 동일한 값의 원소 순서가 유지된다.

단점

• 비교적 많은 수의 이동을 포함한다.
• 비교할 수가 많고 크기가 클 경우에 적합하지 않다. 배열의 길이가 길어질수록 비효율적이다.
• 평균과 최악의 시간 복잡도가 O(N^2)이므로 비효율적이다.

삽입 정렬의 활용

삽입 정렬은 작은 데이터셋이나 거의 정렬된 데이터셋에 대해 매우 효율적이다. 이 알고리즘은 다른 정렬 알고리즘의 일부로 사용되기도 한다. 예를 들어, 퀵 정렬이나 병합 정렬에서 데이터셋이 작아지면 삽입 정렬로 전환하여 정렬하는 것이 더 효율적일 수 있다.

So...

삽입 정렬은 간단하고 구현이 쉬운 정렬 알고리즘으로, 작은 데이터셋이나 거의 정렬된 데이터셋에 대해 매우 효율적이다. 그러나 큰 데이터셋에 대해서는 비효율적일 수 있다. 오늘 학습을 통해 삽입 정렬의 동작 원리와 장단점을 이해하고, 이를 적절히 활용할 수 있는 상황을 파악할 수 있었다.