[java] 삽입 정렬 알고리즘

15 Dec 2023

java

삽입 정렬은 간단하지만 효율적인 정렬 알고리즘입니다. 이 알고리즘은 리스트를 순차적으로 탐색하면서 각 요소를 적절한 위치에 삽입하여 정렬합니다.

삽입 정렬 알고리즘 동작 방식

리스트의 두 번째 요소부터 시작하여 삽입할 대상을 선택합니다.
삽입할 대상을 이미 정렬된 부분의 적절한 위치에 삽입합니다.
대상을 삽입한 후, 다음 요소를 선택하고 위의 과정을 반복합니다.

Java로 구현한 삽입 정렬 알고리즘 예제

public class InsertionSort {
    public void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
 
            /* Move elements of arr[0..i-1], that are
               greater than key, to one position ahead
               of their current position */
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}

위의 예제는 주어진 배열을 오름차순으로 삽입 정렬하는 Java 코드입니다.

삽입 정렬은 작은 크기의 리스트에 효과적이며, 이미 대부분이 정렬되어 있는 경우에도 빠르게 동작합니다.

참고 문헌: