[Algorithm] 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다.
정렬되지 않은 목록(리스트, 배열)을 정렬된 부분과 정렬되지 않은 부분으로 나누며 정렬되지 않은 부분의 원소를 하나씩 선택하여 정렬된 부분의 적절한 위치에 삽입하는 방식으로 동작합니다.

출처

예제

먼저 다음과 같이 정렬되지 않은 배열이 있다고 가정하겠습니다.

위 배열을 오름차순으로 정렬하기 위한 삽입 정렬 알고리즘은 다음과 같이 동작합니다.

0 번째 인덱스 요소인 5는 정렬된 상태로 가정을하고 그 외 나머지 1... n-1 인덱스 요소는 정렬되지 않은 배열이라고 가정합니다.

첫 번쨰 요소를 정렬된 하위 배열의 요소와 비교합니다.
더 크면 첫 번째 요소 앞에 삽입하고 그렇지 않으면 뒤에 삽입합니다.
이제 해당 배열은 정렬된 두 개의 요소가 있고 정렬되지 n - 2개의 요소가 있습니다.

동일하게 정렬되지 않은 배열의 두 번째 요소를 정렬된 마지막 요소와 비교합니다.
작거나 같은 요소는 바로 앞에 삽입합니다.

비교하는 마지막 정렬된 요소보다 작거나 같은 요소를 찾을 때까지 계속 순회하며 적절한 위치에 해당 요소를 삽입합니다.

출처

전체 배열이 정렬될 때까지 정렬되지 않은 하위 배열의 나머지 요소에 대해 위 프로세스를 반복합니다.

시간 복잡도

삽입 정렬은 두 개의 중첩된 반복문을 사용하여 동작하며 각 반복문은 n번씩 반복됩니다.
내부 반복문에서는 현재 원소를 정렬된 부분의 적절한 위치에 삽입하기 위해 이전의 정렬된 원소와 비교합니다.
비교 과정은 최선, 평균, 최악의 경우 모두 수행되며 따라서 시간 복잡도는 O(n^2)가 됩니다.

코드

package io.github.ones1kk.study.sorting;

public class InsertionSort {

    public static void insertionSort(int[] arr, int size) {
        for (int i = 1; i < size; i++) {
            int target = arr[i];

            int j = i - 1;
            while (j >= 0 && target < arr[j]) {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = target;
        }
    }

}

좀 더 자세한 코드는 이 곳에서 확인 가능합니다.

오탈자 및 오류 내용을 댓글 또는 메일로 알려주시면, 검토 후 조치하겠습니다.