[Algorithm] 삽입 정렬(Insert Sort)

2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후,
원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘

 

public class p03_insertSort {

    // 오름차순
    public static int[] solution(int n, int[] arr){
        for(int i = 1; i < n; i++){ // 삽입 대상 순회
            int tmp = arr[i]; // 삽입 대상
            int j;
            for(j = i-1; j >= 0; j--){// i번째 이전을 순회하면서 삽입 대상을 어디에 삽입할지 선택
                if(arr[j] > tmp)
                    arr[j+1] = arr[j];
                else break; // arr[j] < tmp 이면 j이전 인덱스의 값들이 tmp보다 작은 값이다.
            }
            arr[j+1] = tmp; // j번째 에서 else에 의해 for문을 빠져 나왔으므로, j+1 이전은 tmp보다 작은 값이고, j 이후는 tmp보다 큰 값을 갖고 있다.
        }
        return arr;
    }

    // 내림차순
    public static int[] solution2(int n, int[] arr){
        for(int i = 1; i < n; i++){ // 삽입 대상 순회
            int tmp = arr[i]; // 삽입 대상
            int j;
            for(j = i-1; j >= 0; j--) {
                if(arr[j] < tmp) arr[j+1] = arr[j];
                else break;
            }
            arr[j+1] = tmp;
        }
        return arr;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();

        int[] answer = solution(n, arr);
        for(int x: answer) System.out.print(x+" ");
    }
}

 

시간복잡도

최선의 경우(모두 정렬된 경우) O(n), 최악의 경우(역으로 정렬되어 있는 경우) O(n^2)

 

공간복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n) 이다.

 

장점

• 대부분의 원소가 정렬되어 있는 경우 효율적
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort) 이다.
• Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠르다.

 

단점

• 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.
• Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적이다.

 

---

source

https://gyoogle.dev/blog/algorithm/Insertion%20Sort.html

삽입 정렬(Insertion Sort) | 👨🏻‍💻 Tech Interview