버킷 정렬 알고리즘(Java, Python, C/C++ 코드 예제)

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

Bin 정렬이라고도 하는 버킷 정렬은 정렬되지 않은 배열을 입력으로 받아들이고 결과로 정렬된 배열을 생성하는 비교 정렬 방법입니다. 이 방법은 요소를 여러 버킷에 분산하고 삽입 정렬과 같은 정렬 알고리즘을 사용하여 각 버킷을 개별적으로 정렬하는 방식으로 작동합니다. 그런 다음 모든 버킷이 함께 병합되어 정렬된 배열을 형성합니다.

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

  1. 부동 소수점 값
  2. 범위에 걸쳐 균일하게 분포됨

버킷소트의 타임컴plexity는 사용된 버킷 수와 입력 분포의 균일성에 따라 달라집니다. 다음과 같은 다양한 정렬 알고리즘이 있지만 쉘 정렬, 병합 정렬, 힙 정렬 및 퀵 정렬 최상의 시간을 얻을 수 있습니다.plexO(n*logn)의 경우, 버킷 정렬 알고리즘은 선형 시간 com에서 동일한 결과를 얻을 수 있습니다.plexity 또는 O(n).

버킷 정렬은 분산 수집 방식을 따릅니다. 이 접근 방식을 적용하면 요소가 해당 버킷에 분산되고, 버킷에서 정렬되고, 마지막 단계로 수집되어 정렬된 배열을 형성합니다. 이 분산-수집 접근 방식은 다음에서 논의됩니다.wing 섹션에 있어야 합니다.

분산-수집-접근

대규모, complex 문제는 때때로 해결하기 어려울 수 있습니다. 분산-수집 방식은 전체 데이터 세트를 클러스터로 나누어 이러한 문제를 해결하려고 시도합니다. 그런 다음 각 클러스터를 개별적으로 처리하고 모든 것을 다시 모아 최종 답변을 얻습니다.

버킷 정렬 알고리즘이 분산 수집 방법을 구현하는 방법은 다음과 같습니다.

분산-수집-접근

버킷 정렬 작동 방식

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

  1. 빈 버킷 세트가 생성됩니다. 다양한 정책에 따라 버킷 수가 다를 수 있습니다.
  2. 입력 배열에서 각 요소를 해당 버킷에 넣습니다.
  3. 해당 버킷을 개별적으로 정렬합니다.
  4. 정렬된 버킷을 연결하여 단일 출력 배열을 만듭니다.

자세한 작업 단계는 다음과 같습니다.wing 섹션을 참조하십시오.

의사 코드

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: 부동 소수점 숫자에 대한 버킷 정렬 알고리즘

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

단계 1) 첫 번째 버킷에 [10, 0.0) 범위 내의 숫자가 포함되도록 0.1개의 빈 버킷을 만듭니다. 그런 다음 두 번째 버킷에는 [0.1, 0.2) 등이 포함됩니다.

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

      ㅏ. 다음 공식을 사용하여 버킷 인덱스를 계산합니다.
      버킷 인덱스= no_of_buckets *array_element
      비. 버킷[bucket_index]에 요소를 삽입합니다.

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

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

버킷 정렬의 예를 살펴보겠습니다. 이 예에서는 follo를 정렬합니다.wing 버킷 정렬 알고리즘을 사용한 배열-

부동 소수점 숫자에 대한 버킷 정렬 알고리즘

단계 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]에 저장됩니다.

부동 소수점 숫자에 대한 버킷 정렬 알고리즘

모든 배열 요소를 반복한 후 버킷은 다음과 같습니다.wing:

부동 소수점 숫자에 대한 버킷 정렬 알고리즘

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

부동 소수점 숫자에 대한 버킷 정렬 알고리즘

단계 4) 마지막 단계에서는 버킷이 단일 배열로 연결됩니다. 해당 배열은 입력의 정렬된 결과가 됩니다.

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

부동 소수점 숫자에 대한 버킷 정렬 알고리즘

마지막 버킷 요소의 연결은 다음과 같습니다.wing:

부동 소수점 숫자에 대한 버킷 정렬 알고리즘

연결 후 결과 배열은 원하는 정렬 배열이 됩니다.

부동 소수점 숫자에 대한 버킷 정렬 알고리즘

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) 모든 버킷을 단일 배열로 연결합니다.

이 버킷 정렬 알고리즘의 예를 살펴보겠습니다. 이 예에서는 follo를 정렬합니다.wing 버킷 정렬 알고리즘을 사용한 배열-

정수 요소에 대한 버킷 정렬 알고리즘

단계 1) 첫 번째 단계에서는 주어진 배열의 최대 및 최소 요소를 찾아야 합니다. 이 예에서 최대값은 24이고 최소값은 1입니다.

단계 2) 이제 빈 버킷 n개를 선택해야 합니다. 이 예에서는 5개의 버킷을 사용합니다. 그런 다음 비어 있는 것으로 초기화하겠습니다.

단계 3) 각 버킷의 범위는 다음과 같이 계산해야 합니다.wing 공식 :
               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

찬반 양론

장점 단점
더 빠른 계산 수행 다른 알고리즘에 비해 더 많은 공간을 소비합니다.
외부 정렬 방법으로 사용할 수 있습니다. 데이터가 균일하게 분포되지 않으면 성능이 저하됩니다.
버킷을 독립적으로 처리할 수 있습니다.

버킷 정렬 컴plex성 분석

버킷소트(Bucket Sort)의 타임컴(Time Com)plexity

  • 베스트케이스컴plexity :모든 배열 요소가 미리 균일하게 분포되고 정렬되어 있는 경우 요소를 해당 버킷에 분산시키는 데 O(n) 시간이 필요합니다. 그런 다음 다음을 사용하여 각 버킷을 정렬합니다. 삽입 정렬 비용은 O(k)입니다. 따라서 전반적인 complexity는 O(n+k)가 됩니다.
  • 평균 케이스 컴plexity :평균적인 경우에는 입력이 균일하게 분포되어 있다고 가정합니다. 따라서 버킷 정렬 알고리즘은 선형 시간 com을 달성합니다.plexO(n+k)의 성질. 여기서 요소를 분산시키는 데는 O(n) 시간이 필요하고 삽입 정렬을 사용하여 요소를 정렬하는 데는 O(k) 시간이 필요합니다.
  • 최악의 경우 컴plexity :최악의 경우에는 요소가 하나 또는 두 개의 특정 버킷에 균일하게 분산 및 집중되지 않습니다. 이 경우 버킷 정렬은 다음과 같이 작동합니다. 버블 정렬 알고리즘. 따라서 최악의 경우에는 Time complex버킷 정렬의 ity는 O(n^2)입니다.

스페이스컴plex버킷 정렬의 종류

버킷소트의 스페이스컴plexity는 O(n*k)입니다. 여기서 n은 요소 수이고 k는 필요한 버킷 수입니다.