[java] 삽입 정렬 알고리즘

04 Dec 2023

java

삽입 정렬 알고리즘은 간단하지만 효율적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 배열을 순회하면서 각 원소를 “적절한 위치”에 삽입하여 정렬하는 방식입니다.

알고리즘 원리

정렬되지 않은 부분 배열의 첫 번째 원소를 선택합니다.
선택한 원소를 이미 정렬된 부분 배열에서 적절한 위치에 삽입합니다.
선택한 원소를 제외한 나머지 원소들을 한 칸씩 오른쪽으로 이동시킵니다.
반복하여 모든 원소가 정렬될 때까지 위 과정을 반복합니다.

구현 예시

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

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

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 6, 1, 3, 7, 4};
        insertionSort(arr);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

위 예시에서는 삽입 정렬을 구현한 InsertionSort 클래스를 보여줍니다. insertionSort 메서드는 배열을 받아와서 삽입 정렬을 수행합니다. main 메서드에서는 삽입 정렬을 테스트하기 위해 배열을 초기화하고 결과를 출력합니다.

시간복잡도

삽입 정렬의 시간복잡도는 최선의 경우 O(n), 평균 및 최악의 경우 O(n^2)입니다. 최선의 경우는 이미 정렬된 배열을 입력으로 받을 때이며, 삽입 정렬의 특징 중 하나입니다.

알고리즘 원리

구현 예시

시간복잡도

참고 자료