[c++] 이진삽입 정렬

12 Dec 2023

개요

이진 삽입 정렬은 삽입 정렬의 한 변종으로, 두 번째 숫자부터 시작하여 올바른 위치에 삽입하는 것이 아니라 이진 검색을 사용하여 올바른 위치를 찾아 삽입합니다. 이 방법은 대량의 데이터를 정렬할 때 삽입 정렬의 성능을 향상시킬 수 있습니다.

구현

아래는 C++로 작성된 이진 삽입 정렬의 예시입니다.

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& arr, int low, int high, int key) {
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < key) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

void binaryInsertionSort(vector<int>& arr) {
    for (int i = 1; i < arr.size(); i++) {
        int selected = arr[i];
        int j = i - 1;
        int loc = binarySearch(arr, 0, j, selected);
        while (j >= loc) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = selected;
    }
}

int main() {
    vector<int> arr = {5, 2, 7, 3, 9, 1};
    binaryInsertionSort(arr);
    for (int num : arr) {
      cout << num << " ";
    }
    return 0;
}

위의 코드는 배열을 입력 받아 이진 삽입 정렬을 수행하고, 정렬된 배열을 출력합니다.

결론

이진 삽입 정렬은 삽입 정렬을 최적화한 알고리즘으로, 데이터 양이 많은 경우에 더 효율적으로 동작할 수 있습니다. 배열의 길이가 짧은 경우에는 성능 향상이 미미하므로, 사용하는 상황을 고려하여 적절히 선택하는 것이 중요합니다.