초보 자바 프로그래밍(20) - 삽입정렬 (Insertion Sort)

삽입 정렬 대표 이미지

🔖 INDEX

 

 

삽입 정렬(Insertion Sort)은 간단한 비교 기반 정렬 알고리즘 중 하나로, 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어 정렬되지 않은 부분의 원소를 정렬된 부분에 적절한 위치에 삽입하는 방식으로 정렬을 수행합니다. 삽입 정렬은 작은 데이터 셋이나 거의 정렬된 데이터 셋에서 효율적으로 작동하며, 구현이 간단합니다.

 

삽입 정렬의 작동 원리

삽입 정렬의 작동 원리는 다음과 같습니다:

1. 배열의 두 번째 원소부터 시작하여 정렬되지 않은 부분의 첫 번째 원소를 선택합니다.
2. 선택한 원소를 정렬된 부분에서 적절한 위치에 삽입하기 위해, 정렬된 부분의 원소들과 비교하면서 왼쪽으로 이동합니다. 삽입할 위치를 찾을 때까지 이 과정을 반복합니다.
3. 적절한 위치를 찾으면, 선택한 원소를 그 위치에 삽입합니다.
4. 이 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다. ​

 

삽입 정렬의 특징

삽입 정렬의 특징은 다음과 같습니다: ​

1. 안정적인 정렬(Stable Sort): 같은 값의 원소들은 정렬 과정에서 상대적인 순서가 변경되지 않습니다.
2. 제자리 정렬(In-place Sort): 추가적인 메모리를 사용하지 않고 입력 배열 안에서 정렬이 이루어집니다.
3. 시간 복잡도(Time Complexity): 평균적으로 O(n^2)의 시간 복잡도를 가지며, 최악의 경우에도 O(n^2)의 시간이 소요됩니다. 하지만 이미 거의 정렬된 데이터에 대해서는 최선의 경우 O(n)의 시간 복잡도를 가질 수 있습니다.
4. 적응 정렬(Adaptive Sort): 이미 정렬된 부분에 대해서는 빠르게 수행할 수 있는 특징이 있습니다.
5. 교환 비용: 삽입 정렬은 원소들을 올바른 위치에 삽입하는 과정에서 교환을 수행하게 됩니다. 만약 교환 비용이 높은 상황에서 정렬이 필요하다면, 다른 정렬 알고리즘을 사용하는 것을 고려해야 합니다. ​

삽입 정렬은 작은 데이터 셋이나 거의 정렬된 데이터 셋에서 효율적으로 작동하는 정렬 알고리즘이지만, 큰 데이터 셋에서는 더 효율적인 알고리즘을 사용하는 것이 좋습니다. 예를 들어 퀵 정렬, 병합 정렬, 힙 정렬 등이 더 큰 데이터 셋에서 더 좋은 성능을 보입니다.

 

 

삽입 정렬의 구현 예제

삽입 정렬은 다음과 같이 구현할 수 있습니다.

// InsertionSort 클래스 선언
public class InsertionSort {
    // 삽입 정렬 알고리즘을 수행하는 함수
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        // 바깥 루프: 배열의 두 번째 원소부터 마지막 원소까지 반복
        for (int i = 1; i < n; i++) {
            // 현재 인덱스의 값을 key 변수에 저장
            int key = arr[i];
            int j = i - 1;
            // 안쪽 루프: key 값보다 큰 원소들을 오른쪽으로 이동
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            // key 값을 적절한 위치에 삽입
            arr[j + 1] = key;
        }
    }

    // 메인 함수
    public static void main(String[] args) {
        // 정렬할 배열
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        // 정렬 전 배열 출력
        System.out.println("Unsorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }

        // 삽입 정렬 실행
        insertionSort(arr);

        // 정렬 후 배열 출력
        System.out.println("\nSorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }
}

삽입 정렬은 간단하고 이해하기 쉬운 알고리즘이지만, 실제 사용 시에는 데이터 셋의 크기와 특성, 정렬의 안정성 요구, 교환 비용 등을 고려하여 다른 정렬 알고리즘(예: 퀵 정렬, 병합 정렬, 힙 정렬 등)을 사용하는 것이 더 효율적일 수 있습니다. 그러나 작은 데이터 셋이나 이미 거의 정렬된 데이터 셋에서는 삽입 정렬이 효율적인 결과를 가져올 수 있습니다.

 

 

이진 삽입 정렬의 구현 예제

이진 삽입 정렬(binary insertion sort)은 삽입 정렬(insertion sort)의 변형된 형태로, 정렬되어야 할 배열의 각 요소를 적절한 위치에 삽입하는 알고리즘입니다. 이진 삽입 정렬은 이진 검색(binary search)을 사용하여 적절한 삽입 위치를 빠르게 찾아내는 것이 특징입니다.

 

자바에서 이진 삽입 정렬은 다음과 같이 구현할 수 있습니다.

// BinaryInsertionSort 클래스 선언
public class BinaryInsertionSort {
    // 이진 삽입 정렬 알고리즘을 수행하는 함수
    public static void sort(int[] array) {
        // 바깥 루프: 배열의 두 번째 원소부터 마지막 원소까지 반복
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            // 이진 검색을 사용하여 key 값을 삽입할 위치를 찾음
            int index = binarySearch(array, key, 0, i - 1);

            // 원소를 오른쪽으로 이동하여 key 값을 적절한 위치에 삽입할 공간을 만듦
            System.arraycopy(array, index, array, index + 1, i - index);
            // key 값을 적절한 위치에 삽입
            array[index] = key;
        }
    }

    // 이진 검색을 수행하는 함수
    private static int binarySearch(int[] array, int key, int low, int high) {
        // 이진 검색을 통해 key 값이 삽입될 위치를 찾음
        while (low <= high) {
            int mid = (low + high) / 2;
            if (array[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }
}

 

이진 삽입 정렬의 장단점

이진 삽입 정렬이 일반 삽입 정렬과 비교했을 때 가지는 장점 및 단점은 다음과 같습니다.

 

장점:

1. 이진 검색을 사용해 적절한 삽입 위치를 찾기 때문에, 이미 정렬된 데이터에서는 일반 삽입 정렬보다 더 빠른 성능을 발휘합니다.
2. 평균적인 경우, 시간 복잡도가 O(n log n)으로 일반 삽입 정렬의 O(n^2)보다 빠르게 동작합니다.

 

단점:

1. 코드가 삽입 정렬보다 약간 더 복잡합니다.
2. 정렬되지 않은 데이터에서는 일반 삽입 정렬과 큰 성능 차이를 보이지 않을 수 있습니다.
3. 배열의 크기가 매우 클 경우 이진 삽입 정렬의 성능이 떨어지는 경우가 있습니다. 이때는 다른 정렬 알고리즘(예: 퀵 정렬, 병합 정렬 등)을 사용하는 것이 더 효율적일 수 있습니다.