삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)은 기본적인 정렬 알고리즘 중 하나로, 각 요소를 이미 정렬된 배열 부분에 적절한 위치에 삽입하는 방식이다. 이 방법은 작은 데이터 세트에 효과적이며, 구현이 간단하다.

정렬 단계

1 첫 번째 요소 시작: 배열의 첫 번째 요소는 이미 정렬된 것으로 간주한다.

2 다음 요소 선택: 정렬되지 않은 부분에서 다음 요소를 선택한다.

3 적절한 위치에 삽입: 이 요소를 이미 정렬된 배열 부분에 적절한 위치에 삽입한다. 이를 위해, 선택된 요소가 정렬된 부분의 요소보다 크지 않은 위치를 찾을 때까지 정렬된 부분의 요소들을 오른쪽으로 이동시킨다.

4 반복: 모든 요소가 정렬될 때까지 2번과 3번 단계를 반복한다.

삽입 정렬의 시간 복잡도는 평균과 최악의 경우에 O(n^2)이다. 하지만 이미 거의 정렬된 배열에 대해서는 매우 빠르게 동작할 수 있다. 또한, 작은 데이터 세트에 대해서는 다른 복잡한 정렬 알고리즘보다 더 효율적일 수 있다.

구현

    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int current = array[i]; // 정렬되지 않은 부분의 첫 번째 요소
            int j = i - 1;

            // 'current'보다 큰 요소들을 오른쪽으로 이동
            while (j >= 0 && array[j] > current) {
                array[j + 1] = array[j];
                j--;
            }

            // 'current'를 적절한 위치에 삽입
            array[j + 1] = current;
        }
    }