Insertion Sort(삽입 정렬)

출처 : https://en.wikipedia.org/wiki/Insertion_sort

Goal

• 삽입 정렬을 알아보자
• in-place(제자리) 정렬이 무엇인지 설명할 수 있다

Introduction

삽입 정렬은 간단하면서도 효율적인 정렬 알고리즘 중 하나입니다. 평균적인 시간 복잡도는 Big O(n^2)입니다.

정렬 방식

삽입 정렬은 요소를 배열에 삽입하면서 배열을 정렬된 부분과 정렬되지 않는 부분으로 나누어가며 작동합니다. 정렬되지 않는 부분에서 하나의 요소를 선택하여 정렬된 부분의 적절한 위치에 삽입합니다. 이 과정을 반복하여 전체 배열이 정렬될 때까지 진행합니다.

1. 배열의 두 번째 요소부터 시작합니다
2. 현재 요소를 key로 선택합니다
3. key와 이전의 정렬된 요소들을 비교하여 key보다 큰 요소를 찾을 때까지 반복합니다.
4. key보다 큰 요소를 찾으면 해당 요소 다음 위치에 key를 삽입합니다.
5. 배열의 모든 요소에 대해 위의 과정을 반복합니다.

in-place(제자리 정렬)

삽입 정렬은 in-place정렬(제자리 정렬)이기 때문에 입력으로 주어진 데이터를 추가적인 메모리 공간 없이(혹은 제한된 상수 공간만을 사용하여) 원래의 데이터 자체를 수정하면서 문제를 해결하는 알고리즘입니다. 즉, 입력 데이터를 정렬하거나 변형하는 등의 작업을 수행할 때, 원본 데이터를 조작하여 결과를 얻는 것을 의미합니다.

stable(안정 정렬)

삽입 정렬은 stable정렬(안정 정렬)으로 정렬된 결과에서 동일한 값을 가진 원소들의 상대적인 순서가 정렬 이전과 동일하게 유지됩니다. 예를 들어, 동일한 값을 가진 원소 A와 B가 있을 때, A가 B보다 앞에 위치한 상태에서 정렬을 수행하고 나면 정렬된 결과에서도 A가 B보다 앞에 위치해야 합니다.

삽입 정렬 예제

static void InsertionSortExam() {
    int[] data = new int[]{8, 5, 2, 5, 6, 1, 2, 4, 5, 3, 7, 1, 9};
    for (int i = 1; i < data.length; i++) {
        // i는 1부터 시작하여 배열 끝까지 진행
        int target = data[i];
        // 타겟에는 i번째 요소의 값을 선택

        int j = i - 1;
        // j는 i - 1이다.

        // while 진입 시점에서 target 값은 변하지 않는다.
        // target 값을 기준으로 아래의 while 문으로 배열 전체를 확인
        while (j >= 0 && target < data[j]) {
            // 1. j 값은 0보다 크거나 같아야 하며 --> 배열 가장 밑에까지 내려온다
            // 2. target 값은 data[j]보다 작아야 한다 --> 2가지 target 값과 data[j] 값을 비교한다
            // 즉, j는 배열 0까지 내려오면서 target 값은 변하지 않으며 data[j]의 값만 변화시킨다

            data[j + 1] = data[j];
            // 위에 값을 비교하여 target 값 보다 작은 값이 있다면
            // 3. j + 1 의 위치의 값에다가 j의 값을 대입한다.

            j--;
            // 4. j값을 하나 빼고 다시 위의 while 루틴을 시작
        }

        data[j + 1] = target;
        // 5. 위의 while 문을 거치고 난 후 j + 1 자리에 target 값을 저장하고 다시 for 루틴 시작
    }
    System.out.println(Arrays.toString(data));
    // 출력 : [1, 1, 2, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]
}