[c++] 분배정렬

12 Dec 2023

이 알고리즘은 데이터의 분포에 따라 성능이 달라지는 특징을 가지며, 일반적으로 입력범위가 작고 고르게 분포될 때 가장 효율적으로 동작합니다. 분배정렬은 비교없이 데이터들을 바로 정렬할 수 있기 때문에, 비교 기반 정렬 알고리즘들보다 빠를 수 있습니다. 그러나 데이터가 고르게 분포되어 있지 않을 경우에는 메모리 사용량이 많아질 수 있고, 이로 인해 성능이 저하될 수 있습니다.

아래는 C++에서 분배정렬을 구현한 예시 코드입니다.

#include <iostream>
#include <vector>
#include <algorithm>

void bucketSort(std::vector<float>& arr) {
    int n = arr.size();
    std::vector<std::vector<float>> buckets(n);

    // 각 데이터를 버킷에 할당
    for (int i = 0; i < n; i++) {
        int bucketIndex = n * arr[i];
        buckets[bucketIndex].push_back(arr[i]);
    }

    // 각 버킷을 정렬
    for (int i = 0; i < n; i++) {
        std::sort(buckets[i].begin(), buckets[i].end());
    }

    // 정렬된 데이터를 합치기
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < buckets[i].size(); j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

int main() {
    std::vector<float> arr = {0.8, 0.3, 0.2, 0.6, 0.5, 0.7, 0.1, 0.4, 0.9};
    bucketSort(arr);

    std::cout << "Sorted array: ";
    for (float num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

위의 코드는 주어진 부동소수점 배열을 분배정렬을 사용하여 정렬하는 방법을 보여줍니다. 처음에는 각 값에 따라 적절한 버킷에 할당되며, 그 후에 각 버킷 안의 값들을 정렬하고, 마지막으로 모든 버킷을 순차적으로 합쳐서 정렬된 배열을 얻습니다.