삽입정렬(Insertion Sort)

삽입정렬(Insertion Sort)

개념

손 안의 카드를 정렬하는 방법과 유사합니다.

Insertion Sort는 Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘입니다.

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

로직

데이터가 정렬되어 있음을 가정하고 값을 해당 위치에 삽입하여 정렬하는 방법

1. 정렬은 2번째 위치(index)의 값을 temp에 저장합니다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나갑니다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복합니다.

코드

InsertionSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class InsertionSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }
}

console

정렬 전: [81, 14, 9, 34, 0, 88, 41, 89, 71, 26]
정렬 후: [0, 9, 14, 26, 34, 41, 71, 81, 88, 89]

시간복잡도

주어진 데이터의 개수가 $n$개일때
$$
\sum_{i=1}^{n-1}i=1+2+3+...+(n-1)=\frac{n(n-1)}{2}
$$
번의 비교를 하게 된다.

삽입정렬의 시간복잡도는 최악의 경우 $O(N^2)$이며

최선의 경우 $O(N)$이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘입니다.

삽입 정렬의 평균 시간복잡도는 $O(N^2)$입니다.

장점

1. 알고리즘이 단순하여 구현이 쉽다
2. 대부분의 원소가 이미 정렬되어 있는 경우 매우 효율적일 수 있다.
3. 추가적인 메모리 공간을 필요로 하지않는다
4. 안정 정렬이다.
5. 다른 $O(N^2)$의 시간복잡도를 갖는 알고리즘에 비해 효율적이다.

단점

1. 평균과 최악의 시간복잡도가 $O(N^2)$으로 비효율적이다.