[Algorithms] 삽입 정렬

삽입 정렬(Insertion Sort)은 정렬 알고리즘 중 하나로, 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어 처리합니다.

배열의 요소를 하나씩 꺼내서 이미 정렬된 부분에서 적절한 위치에 삽입하는 방식으로 동작합니다.

 

삽입 정렬의 동작 과정입니다.

1. 배열의 첫 번째 요소는 이미 정렬된 상태로 간주합니다.
2. 두 번째 요소부터 순차적으로 선택해, 그 요소가 정렬된 부분에서 올바른 위치에 삽입될 때까지 이전 요소들과 비교합니다.
3. 이 과정을 배열의 마지막 요소까지 반복합니다.

삽입 정렬의 시간 복잡도는 최악의 경우(내림차순으로 정렬된 배열) O(n^2)이고, 최선의 경우(이미 정렬된 배열) O(n)입니다.

 

자바 예제 코드

import java.util.Arrays;

public class InsertionSortExample {

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

            // 현재 요소(key)를 정렬된 부분과 비교해 삽입할 위치를 찾음
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j]; // 값을 오른쪽으로 이동
                j = j - 1;
            }
            arr[j + 1] = key; // key를 적절한 위치에 삽입
        }
    }

    public static void main(String[] args) {
        int[] arr = { 12, 11, 13, 5, 6 };

        System.out.println("Before sorting: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("After sorting: " + Arrays.toString(arr));
    }
}

Before sorting: [12, 11, 13, 5, 6]
After sorting: [5, 6, 11, 12, 13]

 

끝.