[java] 자바에서 삽입 정렬 구현하기

15 Dec 2023

java

삽입 정렬(insertion sort)은 간단하면서도 효율적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 비교적 작은 배열에 대해서 성능이 우수합니다.

삽입 정렬 알고리즘 이해하기

삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눕니다. 정렬되지 않은 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬된 부분을 확장해가며 전체 배열을 정렬합니다.

자바로 삽입 정렬 구현하기

아래는 자바를 사용하여 삽입 정렬을 구현한 예시입니다.

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;

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

위 코드는 insertionSort 메서드를 사용하여 정수 배열을 삽입 정렬하는 방법을 보여줍니다.

결론

삽입 정렬은 간단하면서도 효율적이며, 작은 배열에 대해서 우수한 성능을 보입니다. 이 알고리즘을 이해하고 자바로 구현하여 활용하는 것은 중요합니다.

참고 자료

Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne
Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein