버킷 정렬 알고리즘(Java, Python, C/C++ 코드 예)
사라 첸
버킷 정렬이란 무엇입니까?
Bin 정렬이라고도 하는 버킷 정렬은 정렬되지 않은 배열을 입력으로 받아들이고 결과로 정렬된 배열을 생성하는 비교 정렬 방법입니다. 이 방법은 요소를 여러 버킷에 분산하고 삽입 정렬과 같은 정렬 알고리즘을 사용하여 각 버킷을 개별적으로 정렬하는 방식으로 작동합니다. 그런 다음 모든 버킷이 함께 병합되어 정렬된 배열을 형성합니다.
버킷 정렬은 일반적으로 요소가 다음과 같은 경우에 사용됩니다.
- 부동 소수점 값
- 범위에 걸쳐 균일하게 분포됨
버킷 정렬의 시간 복잡도는 사용된 버킷 수와 입력 분포의 균일성에 따라 달라집니다. 쉘 정렬, 병합 정렬, 힙 정렬 및 퀵 정렬 최상의 경우 시간 복잡도인 O(n*logn)을 달성할 수 있고, 버킷 정렬 알고리즘은 선형 시간 복잡도 또는 O(n)으로 동일한 결과를 달성할 수 있습니다.
버킷 정렬은 산포-수집 접근 방식을 따릅니다. 이 접근 방식을 적용하면, 요소는 해당 버킷에 산포되고, 버킷에서 정렬되고, 마지막 단계로 정렬된 배열을 형성하기 위해 수집됩니다. 이 산포-수집 접근 방식은 다음 섹션에서 설명합니다.
분산-수집-접근
대규모의 복잡한 문제는 때때로 해결하기 어려울 수 있습니다. 분산-수집 접근 방식은 전체 데이터 세트를 클러스터로 나누어 이러한 문제를 해결하려고 시도합니다. 그런 다음 각 클러스터를 별도로 처리하고 모든 것을 다시 모아 최종 답을 얻습니다.
버킷 정렬 알고리즘이 분산 수집 방법을 구현하는 방법은 다음과 같습니다.
버킷 정렬 작동 방식
버킷 정렬의 기본 작동 원리는 다음과 같습니다.
- 빈 버킷 세트가 생성됩니다. 다양한 정책에 따라 버킷 수가 다를 수 있습니다.
- 입력 배열에서 각 요소를 해당 버킷에 넣습니다.
- 해당 버킷을 개별적으로 정렬합니다.
- 정렬된 버킷을 연결하여 단일 출력 배열을 만듭니다.
자세한 작업 단계는 다음 섹션에 나와 있습니다.
의사 코드
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, XNUMX) 범위 내의 숫자를 포함하도록 만듭니다.
단계 2) 각 배열 요소에 대해 다음을 수행합니다.
-
ㅏ. 다음 공식을 사용하여 버킷 인덱스를 계산합니다.
버킷 인덱스= no_of_buckets *array_element
-
비. 버킷[bucket_index]에 요소를 삽입합니다.
단계 3) 삽입 정렬을 사용하여 각 버킷을 개별적으로 정렬합니다.
단계 4) 모든 버킷을 단일 배열로 연결합니다.
버킷 정렬 예를 살펴보겠습니다. 이 예에서는 버킷 정렬 알고리즘을 사용하여 다음 배열을 정렬합니다.
단계 1) 먼저, 빈 버킷 10개를 만듭니다. 첫 번째 버킷에는 [0.0, 0.1) 사이의 숫자가 포함됩니다. 그런 다음 두 번째 버킷에는 [0.1, 0.2) 사이의 숫자가 포함됩니다.
단계 2) 각 배열 요소에 대해 버킷 인덱스를 계산하고 요소를 해당 버킷에 배치합니다.
버킷 지수는 다음 공식을 사용하여 계산할 수 있습니다.
bucket_index= no_of_buckets*array_element
버킷 인덱스 계산:
a) 0.78
bucket_index = no_of_buckets*array_element
= 10 * 0.78
= 7.8
따라서 요소 0.78은 버킷[floor(7.8)] 또는 버킷[7]에 저장됩니다.
b) 0.17
bucket_index = no_of_buckets * 배열 요소
= 10 * 0.17
= 1.7
배열 요소 0.17은 bucket[floor(1.7)] 또는 bucket[1]에 저장됩니다.
c) 0.39
bucket_index = no_of_buckets * 배열 요소
= 10 * 0.39
= 3.9
0.39는 버킷[floor(3.9)] 또는 버킷[3]에 저장됩니다.
모든 배열 요소를 반복한 후 버킷은 다음과 같습니다.
단계 3) 그런 다음, 각 버킷은 삽입 정렬을 사용하여 정렬됩니다. 정렬 작업 후 출력은 다음과 같습니다.
단계 4) 마지막 단계에서는 버킷이 단일 배열로 연결됩니다. 해당 배열은 입력의 정렬된 결과가 됩니다.
각 버킷은 출력 배열에 연결됩니다. 예를 들어 두 번째 버킷 요소를 연결하면 다음과 같습니다.
마지막 버킷 요소의 연결은 다음과 같습니다.
연결 후 결과 배열은 원하는 정렬 배열이 됩니다.
C/의 버킷 정렬 프로그램C++
입력:
//Bucket Sort Program in C/C++
//For not having 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: \n";
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 not having 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_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) 11bucket_index = (요소 – 최소)/스팬
=(11-1)/4
=2
따라서 요소 11은 버킷[2]에 저장됩니다.
-
b) 9
bucket_index = (요소 - 최소)/스팬
=(9-1)/4
=2
참고 : 9는 버킷[1]의 경계 요소이므로 이전 요소의 동일한 버킷에 추가하는 대신 버킷[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; 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:\n", 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(k)가 됩니다. 따라서 전체 복잡도는 O(n+k)가 됩니다.
- 평균 케이스 복잡도:평균적인 경우, 입력이 균일하게 분포되어 있다고 가정합니다. 따라서 버킷 정렬 알고리즘은 O(n+k)의 선형 시간 복잡도를 달성합니다. 여기서 요소를 분산하는 데 O(n) 시간이 필요하고 삽입 정렬을 사용하여 해당 요소를 정렬하는 데 O(k) 시간이 필요합니다.
- 최악의 경우 복잡성:최악의 경우에는 요소가 하나 또는 두 개의 특정 버킷에 균일하게 분산 및 집중되지 않습니다. 이 경우 버킷 정렬은 다음과 같이 작동합니다. 버블 정렬 알고리즘. 따라서 최악의 경우 버킷 정렬의 시간 복잡도는 O(n^2)가 됩니다.
버킷 정렬의 공간 복잡도
버킷 정렬의 공간 복잡도는 O(n*k)입니다. 여기서 n은 요소의 수이고 k는 필요한 버킷의 수입니다.