삽입 정렬(Insertion Sort)

삽입 정렬 (Insertion Sort)

삽입 정렬(Insertion Sort)은 정렬 알고리즘 중 간단하면서도 효율적인 방법 중 하나입니다.

삽입 정렬의 핵심 원리는 배열을 두 부분으로 나누어 정렬하는 것입니다. 하나는 이미 정렬된 부분이고, 다른 하나는 아직 정렬되지 않은 부분입니다. 이후 정렬되지 않은 부분의 원소를 정렬된 부분의 적절한 위치에 '삽입'하는 방식으로 전체 배열을 정렬하게 됩니다.

 

정렬되지 않은 부분의 원소를 정렬된 부분의 적절한 위치에 삽입하는 방식으로 정렬을 수행합니다.

 

삽입 정렬의 과정은 다음과 같습니다.

1. 배열의 두 번째 원소부터 시작하여 정렬되지 않은 부분의 첫 번째 원소까지 반복합니다.
2. 현재 원소를 정렬된 부분에서 적절한 위치에 삽입합니다.
3. 위의 과정을 정렬되지 않은 부분의 마지막 원소까지 반복합니다.
4. 위의 과정을 배열의 크기만큼 반복하면, 배열이 정렬된 상태가 됩니다.

아래는 삽입 정렬의 동작 원리를 그림으로 나타낸 것입니다.

 

출처: https://en.wikipedia.org/wiki/Insertion_sort#Algorithm

 

삽입 정렬의 시간 복잡도는 평균적으로 O(n^2)입니다. 하지만 최선의 경우, 즉 입력 배열이 이미 정렬된 상태라면 O(n)의 시간 복잡도를 가집니다.

Java에서의 삽입 정렬 사용

다음은 자바에서의 삽입 정렬 구현 코드입니다:

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;
    }
}

이 코드는 배열의 두 번째 원소부터 시작하여, 각 원소를 정렬된 부분의 적절한 위치에 삽입하는 과정을 반복합니다. 이를 통해 전체 배열이 정렬되는 것입니다.