[Algorithm] 삽입정렬

2d3k commented 1 year ago

1. 구현 방법

2. 시간복잡도, 공간복잡도

3. 장단점

2d3k commented 1 year ago

1

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

삽입정렬 알고리즘은 배열을 처음부터 끝까지 순회하면서 현재 위치에서 이전 위치들과 비교하며 자신의 위치를 찾아 삽입합니다.

2 삽입정렬의 시간 복잡도는 입력 데이터의 크기에 비례합니다. 즉, 입력 데이터의 크기가 n일 때, 시간 복잡도는 O(n^2)입니다. 이는 배열의 모든 요소를 비교하며 정렬하기 때문입니다.

삽입정렬의 공간 복잡도는 입력 데이터의 크기에 비례합니다. 입력 데이터를 정렬하는 데 추가적인 공간이 필요하지 않기 때문입니다. 따라서, 삽입정렬의 공간 복잡도는 O(n)입니다.

3 삽입정렬의 장점:

구현이 간단하다. 작은 크기의 입력 데이터에 대해서는 다른 정렬 알고리즘보다 빠르다. 입력 데이터가 이미 정렬되어 있는 경우, 최선의 경우 시간 복잡도는 O(n)이 된다. 삽입정렬의 단점:

입력 데이터가 정렬되어 있지 않은 경우, 최악의 경우 시간 복잡도는 O(n^2)이 된다. 입력 데이터의 크기가 커질수록 비효율적이다. 다른 정렬 알고리즘보다 느리다. 안정성을 보장하지 않는다. 같은 값에 대해서 상대적인 순서가 변경될 수 있다. 따라서, 입력 데이터가 작은 경우나 이미 정렬된 경우에는 삽입정렬이 유용할 수 있지만, 입력 데이터가 큰 경우나 안정적인 정렬이 필요한 경우에는 다른 정렬 알고리즘을 사용하는 것이 좋습니다.

hyeonayou commented 1 year ago

삽입 정렬은 현재 비교하고자 하는 target(타겟)과 그 이전의 원소들과 비교하며 자리를 교환(swap)하는 정렬 방법이다.


public class Insertion_Sort {

public static void insertion_sort(int[] a) {
    insertion_sort(a, a.length);
}

private static void insertion_sort(int[] a, int size) {

    for(int i = 1; i < size; i++) {
        // 타겟 넘버
        int target = a[i];

        int j = i - 1;

        // 타겟이 이전 원소보다 크기 전 까지 반복
        while(j >= 0 && target < a[j]) {
            a[j + 1] = a[j];    // 이전 원소를 한 칸씩 뒤로 미룬다.
            j--;
        }

        /*
         * 위 반복문에서 탈출 하는 경우 앞의 원소가 타겟보다 작다는 의미이므로
         * 타겟 원소는 j번째 원소 뒤에 와야한다.
         * 그러므로 타겟은 j + 1 에 위치하게 된다.
         */
        a[j + 1] = target;  
    }

}
}

hyeonayou commented 1 year ago

2. 시간복잡도 : O(n^2) 공간복잡도 : 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다. 3. [장점]

추가적인 메모리 소비가 작다.
거의 정렬 된 경우 매우 효율적이다. 즉, 최선의 경우 O(N)의 시간복잡도를 갖는다.
안장정렬이 가능하다.

[단점]

역순에 가까울 수록 매우 비효율적이다. 즉, 최악의 경우 O(N2)의 시간 복잡도를 갖는다.
데이터의 상태에 따라서 성능 편차가 매우 크다.

2d3k / CS-Study