[JAVA] 삽입정렬(insertion sort)

삽입 정렬 (Insertion Sort)

삽입 정렬은 간단하고 직관적인 정렬 알고리즘으로, 데이터가 거의 정렬된 상태일 때 효율적입니다. 이 알고리즘은 배열을 두 부분으로 나누어, 왼쪽 부분은 정렬된 상태로 유지하고 오른쪽 부분에서 하나씩 요소를 선택하여 적절한 위치에 삽입하는 방식으로 작동합니다.

알고리즘 설명

1. 초기 상태: 첫 번째 요소는 정렬된 상태로 간주합니다.
2. 요소 선택: 두 번째 요소부터 시작하여, 현재 요소를 정렬된 부분과 비교합니다.
3. 삽입 위치 찾기: 현재 요소보다 큰 요소를 찾을 때까지 정렬된 부분을 왼쪽으로 이동합니다.
4. 삽입: 적절한 위치에 현재 요소를 삽입합니다.
5. 반복: 모든 요소에 대해 위 과정을 반복합니다.

시간 복잡도

• 최악의 경우: O(n^2)
• 평균 경우: O(n^2)
• 최선의 경우: O(n) (이미 정렬된 경우)

Java 소스코드

아래는 Java로 구현한 삽입 정렬의 예시입니다.

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

            // 정렬된 부분에서 key보다 큰 요소를 오른쪽으로 이동
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            // key를 적절한 위치에 삽입
            array[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 5, 6};
        insertionSort(array);
        
        // 정렬된 배열 출력
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

 

삽입 정렬은 구현이 간단하고, 특히 데이터가 거의 정렬된 경우에 매우 빠릅니다. 하지만 데이터 양이 많아질수록 비효율적이므로, 대량의 데이터를 정렬할 때는 다른 정렬 알고리즘을 고려하는 것이 좋습니다.