버킷 정렬 알고리즘(Java, Python, C/C++ Code 예시)

⚡ 스마트 요약

버킷 정렬은 입력 요소를 여러 버킷에 분산시키고, 각 버킷을 독립적으로 정렬한 다음, 최종적으로 정렬된 배열을 생성합니다.

🪣 핵심 아이디어: 버킷 정렬은 값을 여러 버킷으로 나누고, 각 버킷을 정렬한 다음, 순서대로 연결합니다.
📊 가장 적합한 것: 버킷 정렬은 [0.0, 1.0] 범위의 균일하게 분포된 부동 소수점 값 또는 고르게 분포된 정수 값에 대해 가장 잘 작동합니다.
⚡ 시간 복잡성 : 평균 및 최상의 경우는 O(n+k)의 선형 시간 복잡도를 가지며, 최악의 경우는 O(n²)으로 저하됩니다.
✅ 장점: 버킷은 병렬로 처리할 수 있으므로 대규모 데이터 세트의 외부 정렬에 적합합니다.
🧪 구현 : Code C에서, C++, Python예산 및 Java 부동 소수점 및 정수형 변형을 모두 보여줍니다.

버킷 정렬이란 무엇입니까?

버킷 정렬(또는 빈 정렬)은 비교 기반 분산 정렬 방법으로, 정렬되지 않은 배열을 입력으로 받아 정렬된 배열을 출력합니다. 이 기법은 배열의 요소를 여러 개의 버킷으로 나누고, 각 버킷에 있는 요소들을 삽입 정렬과 같은 다른 정렬 알고리즘을 사용하여 개별적으로 정렬합니다. 마지막으로 모든 버킷의 요소들을 병합하여 최종적으로 정렬된 배열을 만듭니다.

버킷 정렬은 일반적으로 다음과 같은 요소에 사용됩니다.

부동 소수점 값
알려진 범위에 걸쳐 균일하게 분포됨

버킷 정렬의 시간 복잡도는 사용되는 버킷의 개수와 입력 분포의 균일성에 따라 달라집니다. 다른 정렬 알고리즘(예: ...)은 시간 복잡도가 다릅니다. 쉘 정렬, 병합 정렬, 힙 정렬 및 퀵 정렬 버킷 정렬 알고리즘은 최상의 경우 시간 복잡도가 O(n*logn)이지만, 유리한 조건에서는 선형 시간 복잡도 O(n)에 도달할 수 있습니다.

버킷 정렬은 분산-수집 방식을 따릅니다. 요소들은 대응하는 버킷에 분산되고, 각 버킷 내부에서 정렬된 후, 마지막 단계에서 정렬된 배열을 형성하기 위해 모아집니다. 이러한 분산-수집 방식은 다음 절에서 자세히 설명합니다.

분산-집계 접근법

규모가 크고 복잡한 문제는 직접 해결하기 어려운 경우가 있습니다. 분산-수집 접근 방식은 전체 데이터 세트를 클러스터로 나누어 이러한 문제를 해결합니다. 각 클러스터는 개별적으로 처리된 후, 결과를 다시 통합하여 최종 해답을 도출합니다.

다음은 버킷 정렬 알고리즘이 분산-모으기 방식을 구현하는 방법입니다.

버킷 정렬 작동 방식

버킷 정렬의 기본 작동 원리는 다음과 같습니다.

빈 버킷 세트가 생성됩니다. 선택한 정책에 따라 버킷의 개수는 달라질 수 있습니다.
입력 배열의 각 요소는 해당 버킷에 배치됩니다.
각 버킷은 보조 정렬 알고리즘을 사용하여 개별적으로 정렬됩니다.
정렬된 버킷들을 연결하여 단일 출력 배열을 생성합니다.

별명 Code

Start
Create N empty buckets
For each array element:
    Calculate bucket index
    Put that element into the corresponding bucket
For each bucket:
    Sort elements within each bucket
Merge all the elements from each bucket
Output the sorted array
End

방법 1: 부동 소수점에 대한 버킷 정렬 알고리즘 Numbers

[0.0, 1.0] 범위의 부동 소수점 숫자에 대한 버킷 정렬 알고리즘:

단계 1) 10개의 빈 버킷을 생성합니다. 첫 번째 버킷에는 [0.0, 0.1) 범위의 숫자가 저장되고, 두 번째 버킷에는 [0.1, 0.2) 범위의 숫자가 저장되며, 이런 식으로 계속됩니다.

단계 2) 각 배열 요소에 대해 다음을 수행합니다.

a. 다음 공식을 사용하여 버킷 인덱스를 계산하십시오.
bucket_index = 버킷 수 * 배열 요소
b. 해당 요소를 bucket[bucket_index]에 삽입합니다.

단계 3) 삽입 정렬을 사용하여 각 버킷을 개별적으로 정렬합니다.

단계 4) 모든 버킷을 하나의 정렬된 배열로 연결합니다.

버킷 정렬 예제를 살펴보겠습니다. 이 예제에서는 다음 배열을 정렬합니다.

단계 1) 먼저, 10개의 빈 버킷을 생성합니다. 첫 번째 버킷에는 [0.0, 0.1) 범위의 숫자가, 두 번째 버킷에는 [0.1, 0.2) 범위의 숫자가, 이런 식으로 계속됩니다.

단계 2) 배열의 각 요소에 대해 버킷 인덱스를 계산하고 해당 요소를 해당 버킷에 배치합니다.

버킷 인덱스는 다음 공식을 사용하여 계산됩니다.
bucket_index = 버킷 수 * 배열 요소

버킷 인덱스 계산:
a) 0.78
      bucket_index = 버킷 수 * 배열 요소
              = 10 * 0.78
              = 7.8
따라서 요소 0.78은 bucket[floor(7.8)] 또는 bucket[7]에 저장됩니다.

b) 0.17
      bucket_index = 버킷 수 * 배열 요소
              = 10 * 0.17
              = 1.7

배열 요소 0.17은 bucket[floor(1.7)] 또는 bucket[1]에 저장됩니다.

c) 0.39
      bucket_index = 버킷 수 * 배열 요소
              = 10 * 0.39
              = 3.9
0.39는 버킷[floor(3.9)] 또는 버킷[3]에 저장됩니다.

배열의 모든 요소를 순회한 후, 버킷은 다음과 같습니다.

단계 3) 각 버킷은 삽입 정렬을 사용하여 정렬됩니다. 정렬 작업 후 출력은 다음과 같습니다.

단계 4) 마지막 단계에서는 버킷들을 하나의 배열로 연결합니다. 이 배열이 바로 입력 데이터의 정렬된 결과입니다.

각 버킷의 요소들이 출력 배열에 연결됩니다. 예를 들어, 두 번째 버킷 요소들의 연결은 다음과 같습니다.

마지막 버킷 요소들의 연결은 아래와 같습니다.

문자열을 연결하면 원하는 정렬된 배열이 생성됩니다.

C/의 버킷 정렬 프로그램C++

입력:

//Bucket Sort Program in C/C++
//For values without integer parts
#include <bits/stdc++.h>
#define BUCKET_SIZE 10
using namespace std;
void bucketSort(float input[], int array_size)
{
  vector <float>bucket[BUCKET_SIZE];
  for (int i = 0; i < array_size; i++) {
    int index = BUCKET_SIZE*input[i];
    bucket[index].push_back(input[i]);
  }
  for (int i = 0; i < BUCKET_SIZE; i++)
    sort(bucket[i].begin(), bucket[i].end());
  int out_index = 0;
  for (int i = 0; i < BUCKET_SIZE; i++)
    for (int j = 0; j < bucket[i].size(); j++)
      input[out_index++] = bucket[i][j];
}
int main()
{
  float input[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.69};
  int array_size = sizeof(input)/sizeof(input[0]);

  bucketSort(input, array_size);
  cout <<"Sorted Output: 
";
  for (int i = 0; i< array_size; i++)
    cout<<input[i]<<" ";
  return 0;
}

출력:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

버킷 정렬 프로그램 Python

입력:

# Bucket Sort Program in Python
# For values without integer parts
def bucketSort(input):
    output = []
    bucket_size = 10
    for bucket in range(bucket_size):
        output.append([])
    for element in input:
        index = int(bucket_size * element)
        output[index].append(element)
    for bucket in range(bucket_size):
        output[bucket] = sorted(output[bucket])
    out_index = 0
    for bucket in range(bucket_size):
        for element in range(len(output[bucket])):
            input[out_index] = output[bucket][element]
            out_index += 1
    return input

input = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.69]
print("Sorted Output:")
print(bucketSort(input))

출력:

Sorted Output:
[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]

버킷 정렬 Java

입력:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    private static final int BUCKET_SIZE = 10;
    public static void bucketSort(float[] input, int arraySize) {
        List<Float>[] bucket = new ArrayList[BUCKET_SIZE];
        for (int i = 0; i < arraySize; i++) {
            int index = (int)(BUCKET_SIZE * input[i]);
            if (bucket[index] == null) {
                bucket[index] = new ArrayList<>();
            }
            bucket[index].add(input[i]);
        }
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                Collections.sort(bucket[i]);
            }
        }
        int outIndex = 0;
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                for (float value: bucket[i]) {
                    input[outIndex++] = value;
                }
            }
        }
    }
    public static void main(String[] args) {
        float[] input = {0.78f,0.17f,0.39f,0.26f,0.72f,0.94f,0.21f,0.12f,0.23f,0.69f};
        int arraySize = input.length;
        bucketSort(input, arraySize);
        System.out.println("Sorted Output:");
        for (int i = 0; i < arraySize; i++) {
            System.out.print(input[i]+" ");
        }
    }
}

출력:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

방법 2: 정수 요소에 대한 버킷 정렬 알고리즘

입력값이 [0.0, 1.0] 범위를 벗어나는 경우 버킷 정렬 알고리즘은 이전과 약간 다릅니다. 연산이 경우에 필요한 절차는 다음과 같습니다.

단계 1) 배열에서 최댓값과 최솟값을 찾으세요.

단계 2) 버킷의 개수 n을 선택하고, 모든 버킷을 빈 상태로 초기화합니다.

단계 3) 다음 공식을 사용하여 각 버킷의 범위 또는 범위를 계산합니다.
span = (maximum - minimum) / n

단계 4) 각 배열 요소에 대해 다음을 수행합니다.

1. 버킷 인덱스를 계산합니다.
bucket_index = (element - minimum) / span
2. 해당 요소를 bucket[bucket_index]에 삽입합니다.

단계 5) 삽입 정렬을 사용하여 각 버킷을 정렬합니다.

단계 6) 모든 버킷을 단일 배열로 연결합니다.

버킷 정렬 알고리즘의 예제를 살펴보겠습니다. 이 예제에서는 다음 배열을 정렬합니다.

단계 1) 첫 번째 단계에서는 주어진 배열의 최댓값과 최솟값을 찾습니다. 이 예시에서 최댓값은 24이고 최솟값은 1입니다.

단계 2) 다음으로 빈 버킷의 개수 n을 선택합니다. 이 예시에서는 5개의 버킷을 사용하고 모두 비어 있는 상태로 초기화합니다.

단계 3) 각 버킷의 범위는 다음 공식을 사용하여 계산됩니다.
span = (maximum - minimum) / n = (24 - 1) / 5 = 4

따라서 첫 번째 버킷에는 [0, 5) 범위의 숫자가 포함되고 두 번째 버킷에는 [5, 10) 범위의 숫자가 포함되는 식입니다.

단계 4) 배열의 각 요소에 대해 버킷 인덱스를 계산하고 해당 요소를 해당 버킷에 배치합니다. 버킷 인덱스는 다음 공식을 사용하여 계산됩니다.
bucket_index = (element - minimum) / span

버킷 인덱스 계산:

a) 11
bucket_index = (요소 – 최소값) / span
= (11 – 1) / 4
= 2

따라서 요소 11은 버킷[2]에 저장됩니다.

b) 9
bucket_index = (요소 – 최소값) / span
= (9 – 1) / 4
= 2

참고 : 9는 bucket[1]의 경계 요소이므로 이전 요소와 같은 버킷에 배치되는 대신 bucket[1]에 추가됩니다.

각 요소에 대한 연산을 수행한 후, 버킷은 다음과 같습니다.

단계 5) 이제 각 버킷은 삽입 정렬을 사용하여 정렬됩니다. 정렬 후 버킷은 다음과 같습니다.

단계 6) 마지막 단계에서 버킷들은 하나의 배열로 연결됩니다. 정렬 입력값의 정렬된 결과입니다.

C/의 버킷 정렬 프로그램C++

입력:

#include<bits/stdc++.h>
using namespace std;
void bucketSort(vector < double > & input, int No_Of_Buckets)
{
  double max_value = * max_element(input.begin(), input.end());
  double min_value = * min_element(input.begin(), input.end());
  double span = (max_value - min_value) / No_Of_Buckets;
  vector<vector <double>> output;
  for (int i = 0; i < No_Of_Buckets; i++)
    output.push_back(vector <double>());
  for (int i = 0; i < input.size(); i++)
  {
    double difference = (input[i] - min_value) / span
     - int((input[i] - min_value) / span);
    if (difference == 0 && input[i] != min_value)
      output[int((input[i] - min_value) / span) - 1].push_back(input[i]);
    else
      output[int((input[i] - min_value) / span)].push_back(input[i]);
  }
  for (int i = 0; i < output.size(); i++)
  {
    if (!output[i].empty())
      sort(output[i].begin(), output[i].end());
  }
  int index = 0;
  for (vector <double> & bucket: output)
  {
    if (!bucket.empty())
    {
      for (double i: bucket)
      {
        input[index] = i;
        index++;
      }
    }
  }
}
int main()
{
  vector <double> input ={11,9,21,8,17,19,13,1,24,12};
  int No_Of_Buckets = 5;
  bucketSort(input, No_Of_Buckets);
  cout<<"Sorted Output:";
  for (int i=0; i < input.size(); i++)
    cout <<input[i]<<" ";
  return 0;
}

출력:

Sorted Output:1 8 9 11 12 13 17 19 21 24

버킷 정렬 프로그램 Python

입력:

def bucketSort(input, No_Of_Buckets):
    max_element = max(input)
    min_element = min(input)
    span = (max_element - min_element) / No_Of_Buckets
    output = []
    for bucket in range(No_Of_Buckets):
        output.append([])
    for element in range(len(input)):
        diff = (input[element] - min_element) / span - int(
            (input[element] - min_element) / span
        )
        if diff == 0 and input[element] != min_element:
            output[int((input[element] - min_element) / span) - 1].append(
                input[element]
            )
        else:
            output[int((input[element] - min_element) / span)].append(input[element])
    for bucket in range(len(output)):
        if len(output[bucket]) != 0:
            output[bucket].sort()
    index = 0
    for bucket in output:
        if bucket:
            for element in bucket:
                input[index] = element
                index = index + 1
input = [11, 9, 21, 8, 17, 19, 13, 1, 24, 12]
No_Of_Buckets = 5
bucketSort(input, No_Of_Buckets)
print("Sorted Output:
", input)

출력:

Sorted Output:
[1, 8, 9, 11, 12, 13, 17, 19, 21, 24]

버킷 정렬 Java

입력:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    public static void bucketSort(List < Double > input, int No_Of_Buckets) {
        double max_value = Collections.max(input);
        double min_value = Collections.min(input);
        double span =(max_value - min_value) / No_Of_Buckets;
        List<List<Double>> output = new ArrayList<>();
        for (int i = 0; i < No_Of_Buckets; i++) {
            output.add(new ArrayList<>());
        }
        for (Double value: input) {
            double difference = (value - min_value) / span - ((value - min_value) / span);
            if (difference == 0 && value != min_value) {
                output.get((int)((value - min_value) / span) - 1).add(value);
            } else {
                output.get((int)((value - min_value) / span)).add(value);
            }
        }
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
                Collections.sort(bucket);
            }
        }
        int index = 0;
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
                for (Double value: bucket) {
                    input.set(index,value);
                    index++;
                }
            }
        }
    }
    public static void main(String[] args) {
        List <Double> input = new ArrayList<>();
        input.add(11.0);
        input.add(9.0);
        input.add(21.0);
        input.add(8.0);
        input.add(17.0);
        input.add(19.0);
        input.add(13.0);
        input.add(1.0);
        input.add(24.0);
        input.add(12.0);
        int No_Of_Buckets = 5;
        bucketSort(input, No_Of_Buckets);
        System.out.println("Sorted Output:");
        for (Double value: input) {
            System.out.print(value + " ");
        }
    }
}

출력:

Sorted Output:
1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0

버킷 분류의 장단점

장점	단점
균일하게 분포된 데이터에서 더 빠른 계산을 수행합니다.	제자리 정렬 알고리즘에 비해 더 많은 공간을 차지합니다.
대규모 데이터 세트에 대한 외부 정렬 방법으로 사용할 수 있습니다.	데이터가 균일하게 분포되지 않으면 성능이 저하됩니다.
버킷은 독립적으로 병렬 처리될 수 있습니다.	데이터 범위 및 분포에 대한 사전 지식이 필요합니다.

버킷 정렬 복잡성 분석

버킷 정렬 시간 복잡성

최고의 사례 복잡성: 배열의 모든 요소가 각 버킷 내에 균일하게 분포되어 있고 미리 정렬되어 있는 경우, 요소를 해당 버킷에 분산시키는 데 O(n) 시간이 소요됩니다. 그런 다음 각 버킷을 정렬하는 데 O(n) 시간을 사용합니다. 삽입 정렬 비용은 O(k)입니다. 따라서 전체 복잡도는 O(n+k)입니다.
평균 케이스 복잡도: 일반적인 경우 입력값이 균일하게 분포되어 있다고 가정합니다. 따라서 버킷 정렬 알고리즘은 O(n+k)의 선형 시간 복잡도를 달성합니다. 여기서 O(n) 시간은 요소를 분산하는 데 필요하고 O(k) 시간은 삽입 정렬을 사용하여 정렬하는 데 필요합니다.
최악의 경우 복잡성: 최악의 경우, 요소들이 균일하게 분포되어 있지 않고 하나 또는 두 개의 버킷에 집중됩니다. 이 경우, 버킷 정렬은 다음과 유사한 동작을 보입니다. 버블 정렬 알고리즘따라서 최악의 경우 버킷 정렬의 시간 복잡도는 O(n²)입니다.

버킷 정렬의 공간 복잡도

버킷 정렬의 공간 복잡도는 O(n*k)입니다. 여기서 n은 요소의 개수이고 k는 정렬 과정에서 요소를 담는 데 필요한 버킷의 개수입니다.

자주 묻는 질문

입력값이 알려진 범위, 특히 [0.0, 1.0] 범위의 부동 소수점 숫자에 걸쳐 균일하게 분포되어 있을 때 버킷 정렬을 사용하십시오. 이러한 데이터에서는 선형 시간 복잡도를 보이지만, 분포가 군집되어 있거나 알려지지 않은 경우에는 성능이 저하됩니다.

버킷 정렬은 각 버킷 내부에 사용되는 정렬 알고리즘이 안정적일 때 안정적입니다. 삽입 정렬은 동일한 요소의 상대적 순서를 유지하므로, 삽입 정렬을 사용하는 표준 버킷 정렬 구현은 안정적이라고 간주됩니다.

버킷 정렬은 값 범위별로 요소를 그룹화하고 각 버킷을 다른 알고리즘으로 정렬합니다. 기수 정렬은 숫자를 자릿수별로 그룹화하고 내부적으로 계수 정렬을 사용합니다. 버킷 정렬은 균일 분포 부동 소수점 숫자에 유리하고, 기수 정렬은 고정 너비 정수 또는 문자열에 유리합니다.

버킷 정렬의 최악의 경우 시간 복잡도는 O(n²)입니다. 이는 모든 입력 요소가 하나의 버킷에 속하게 되어 내부 정렬(일반적으로 삽입 정렬)이 제곱 시간 복잡도로 동작하게 되는 경우입니다. 균일 분포는 이러한 상황을 방지합니다.

네. 음수를 처리하려면 최소값과 최대값을 모두 찾은 다음 (요소 - 최소값) / 범위 공식을 사용하여 버킷 인덱스를 계산합니다. 이렇게 하면 음수 값이 음수가 아닌 인덱스 공간으로 이동하고 표준 버킷 정렬 로직은 변경 없이 그대로 진행될 수 있습니다.

VisuAlgo, Algorithm Visualizer, ChatGPT와 같은 AI 기반 플랫폼은 단계별로 알고리즘을 생성합니다. trac이러한 애니메이션은 학습자가 버킷 분류를 시각화하는 데 도움이 됩니다. 분산, 분류 및 수집 단계를 애니메이션으로 보여주어 버킷 인덱스 계산 및 분할 논리를 더 쉽게 이해할 수 있도록 합니다.

AI 기반 추천 시스템은 데이터셋 크기, 값 분포, 메모리 제한 등을 분석하여 적합한 알고리즘을 제안합니다. 예를 들어, 균일하게 분포된 부동소수점 데이터의 경우 버킷 정렬을 선호합니다. 반면, 다양한 정수 범위의 데이터셋에서는 퀵 정렬이나 기수 정렬을 제안할 수 있습니다.

버킷 정렬 알고리즘(Java, Python, C/C++ Code 예시)

버킷 정렬이란 무엇입니까?

분산-집계 접근법

버킷 정렬 작동 방식

별명 Code

방법 1: 부동 소수점에 대한 버킷 정렬 알고리즘 Numbers

C/의 버킷 정렬 프로그램C++

버킷 정렬 프로그램 Python

버킷 정렬 Java

방법 2: 정수 요소에 대한 버킷 정렬 알고리즘

C/의 버킷 정렬 프로그램C++

버킷 정렬 프로그램 Python

버킷 정렬 Java

버킷 분류의 장단점

버킷 정렬 복잡성 분석

버킷 정렬 시간 복잡성

버킷 정렬의 공간 복잡도

자주 묻는 질문

이 게시물을 요약하면 다음과 같습니다.

뉴스레터 신청하기

버킷 정렬이란 무엇입니까?

분산-집계 접근법

버킷 정렬 작동 방식

별명 Code

방법 1: 부동 소수점에 대한 버킷 정렬 알고리즘 Numbers

관련 기사

C/의 버킷 정렬 프로그램C++

버킷 정렬 프로그램 Python

버킷 정렬 Java

방법 2: 정수 요소에 대한 버킷 정렬 알고리즘

C/의 버킷 정렬 프로그램C++

버킷 정렬 프로그램 Python

버킷 정렬 Java

버킷 분류의 장단점

버킷 정렬 복잡성 분석

버킷 정렬 시간 복잡성

버킷 정렬의 공간 복잡도

자주 묻는 질문

이 게시물을 요약하면 다음과 같습니다.

뉴스레터 신청하기