Algorytm sortowania kubełkowego (Java, Python, C/C++ Code Przykłady)

Co to jest sortowanie kubełkowe?

Sortowanie kubełkowe (bucket sort), często nazywane sortowaniem binarnym (bin sort), to metoda sortowania oparta na porównaniach, która przyjmuje nieposortowaną tablicę jako dane wejściowe i generuje posortowaną tablicę jako dane wyjściowe. Technika ta rozdziela elementy na kilka kubełków i sortuje każdy z nich indywidualnie za pomocą innego algorytmu sortowania, takiego jak sortowanie przez wstawianie (insert sort). Następnie wszystkie kubełki są łączone, tworząc ostateczną posortowaną tablicę.

Sortowanie kubełkowe jest powszechnie stosowane, gdy elementami są:

1. Wartości zmiennoprzecinkowe
2. Równomiernie rozłożone w znanym zakresie

Złożoność czasowa sortowania kubełkowego zależy od liczby użytych kubełków i jednorodności rozkładu danych wejściowych. Podczas gdy inne algorytmy sortowania, takie jak sortowanie muszli, sortowanie przez scalanie, sortowanie na stercie i szybkie sortowanie osiągnąć złożoność czasową w najlepszym przypadku na poziomie O(n*logn), algorytm sortowania kubełkowego może osiągnąć liniową złożoność czasową O(n) w sprzyjających warunkach.

Sortowanie kubełkowe opiera się na podejściu rozproszenia i zebrania. Elementy są rozrzucane do odpowiednich kubełków, sortowane w obrębie każdego kubełka i zbierane w celu utworzenia posortowanej tablicy w ostatnim kroku. To podejście rozproszenia i zebrania zostanie omówione w następnej sekcji.

Podejście rozproszenia-zgromadzenia

Problemy o dużej skali i złożone mogą być czasami trudne do bezpośredniego rozwiązania. Podejście rozproszenia i zebrania danych rozwiązuje takie problemy, dzieląc cały zbiór danych na klastry. Każdy klaster jest przetwarzany osobno, a wyniki są ponownie łączone w celu uzyskania ostatecznej odpowiedzi.

Oto w jaki sposób algorytm sortowania kubełkowego implementuje metodę rozproszenia-zbierania:

Jak działa sortowanie kubełkowe

Podstawowa zasada działania sortowania kubełkowego jest następująca:

1. Tworzony jest zestaw pustych kontenerów. Liczba kontenerów może się różnić w zależności od wybranej polityki.
2. Każdy element tablicy wejściowej jest umieszczany w odpowiednim pojemniku.
3. Każdy pojemnik jest sortowany indywidualnie przy użyciu algorytmu sortowania wtórnego.
4. Posortowane pojemniki są łączone w celu utworzenia pojedynczej tablicy wyjściowej.

Rzekomy 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

Metoda 1: Algorytm sortowania segmentowego dla zmiennoprzecinkowego Numbers

Algorytm sortowania kubełkowego dla liczb zmiennoprzecinkowych w zakresie [0.0, 1.0]:

Krok 1) Utwórz dziesięć (10) pustych kontenerów. Pierwszy kontener zawiera liczby z zakresu [0.0, 0.1]. Drugi kontener zawiera liczby z zakresu [0.1, 0.2] itd.

Krok 2) Dla każdego elementu tablicy:

• a. Oblicz indeks wiadra, korzystając ze wzoru:
  indeks_wiadra = liczba_wiader * element_tablicy
• b. Wstaw element do bucket[bucket_index]

Krok 3) Sortuj każdy segment indywidualnie, korzystając z sortowania przez wstawianie.

Krok 4) Połącz wszystkie kontenery w jedną posortowaną tablicę.

Przeanalizujmy przykład sortowania kubełkowego. W tym przykładzie posortujemy następującą tablicę:

Krok 1) Najpierw tworzymy 10 pustych kontenerów. Pierwszy kontener zawiera liczby z przedziału [0.0, 0.1]. Drugi kontener zawiera liczby z przedziału [0.1, 0.2] itd.

Krok 2) Dla każdego elementu tablicy oblicz indeks kontenera i umieść element w tym kontenerze.

Wskaźnik wiadra oblicza się według wzoru:
        indeks_wiadra = liczba_wiader * element_tablicy

Obliczanie indeksu koszyka:
a) 0.78
      indeks_wiadra = liczba_wiader * element_tablicy
              = 10 * 0.78
              = 7.8
Dlatego element 0.78 jest przechowywany w bucket[floor(7.8)] lub bucket[7].

b) 0.17
      indeks_wiadra = liczba_wiader * element_tablicy
              = 10 * 0.17
              = 1.7

Element tablicy 0.17 jest przechowywany w bucket[floor(1.7)] lub bucket[1].

c) 0.39
      indeks_wiadra = liczba_wiader * element_tablicy
              = 10 * 0.39
              = 3.9
0.39 jest przechowywane w wiadrze[floor(3.9)] lub wiadrze[3].

Po przeiterowaniu wszystkich elementów tablicy, zasobniki wyglądają następująco:

Krok 3) Następnie każdy kontener jest sortowany metodą sortowania przez wstawianie. Po operacji sortowania wynik jest następujący:

Krok 4) W ostatnim kroku kontenery są łączone w jedną tablicę. Ta tablica stanowi posortowany wynik danych wejściowych.

Każdy kontener jest łączony z tablicą wyjściową. Na przykład, połączenie elementów drugiego kontenera:

Poniżej pokazano połączenie ostatnich elementów wiadra:

Po połączeniu powstaje tablica, która jest pożądaną posortowaną tablicą.

Program sortowania kubełkowego w C/C++

Wejście:

//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;
}

Wyjście:

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

Program sortowania kubełkowego w Python

Wejście:

# 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))

Wyjście:

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

Sortowanie wiadro Java

Wejście:

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]+" ");
        }
    }
}

Wyjście:

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

Metoda 2: Algorytm sortowania segmentowego dla elementów całkowitych

Algorytm sortowania kubełkowego dla danych wejściowych zawierających liczby spoza zakresu [0.0, 1.0] różni się nieznacznie od poprzedniego algorytmW tym przypadku wymagane są następujące kroki:

Krok 1) Znajdź maksymalny i minimalny element w tablicy.

Krok 2) Wybierz liczbę kontenerów (n) i zainicjuj je jako puste.

Krok 3) Oblicz zasięg lub rozpiętość każdego segmentu, korzystając ze wzoru:
        span = (maximum - minimum) / n

Krok 4) Dla każdego elementu tablicy:

• 1. Oblicz indeks wiadra:
          bucket_index = (element - minimum) / span
• 2. Wstaw element do bucket[bucket_index]

Krok 5) Sortuj każdy segment za pomocą sortowania przez wstawianie.

Krok 6) Połącz wszystkie segmenty w jedną tablicę.

Przyjrzyjmy się przykładowi algorytmu sortowania kubełkowego. W tym przykładzie posortujemy następującą tablicę:

Krok 1) W pierwszym kroku znajdujemy maksymalną i minimalną liczbę elementów danej tablicy. W tym przykładzie maksymalna liczba to 24, a minimalna to 1.

Krok 2) Następnie wybieramy liczbę pustych kontenerów, n. W tym przykładzie używamy 5 kontenerów i inicjujemy je jako puste.

Krok 3) Rozpiętość każdego wiadra obliczana jest przy użyciu wzoru:
        span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Zatem pierwszy przedział zawiera liczby z zakresu [0, 5]. Drugi przedział zawiera liczby z zakresu [5, 10] itd.

Krok 4) Dla każdego elementu tablicy oblicz indeks kontenera i umieść element w tym kontenerze. Indeks kontenera oblicza się za pomocą wzoru:
        bucket_index = (element - minimum) / span

Obliczanie indeksu koszyka:

a) 11
bucket_index = (element – ​​minimum) / rozpiętość
        = (11 – 1) / 4
        = 2

W ten sposób element 11 jest przechowywany w kontenerze[2].

b) 9
bucket_index = (element – ​​minimum) / rozpiętość
        = (9 – 1) / 4
        = 2

Uwaga: Ponieważ 9 jest elementem granicznym dla bucket[1], jest dołączany do bucket[1] zamiast być umieszczany w tym samym bucket co poprzedni element.

Po wykonaniu operacji dla każdego elementu, zasobniki wyglądają następująco:

Krok 5) Teraz każdy koszyk jest sortowany metodą sortowania przez wstawianie. Koszyki po sortowaniu:

Krok 6) W ostatnim kroku wiadra są łączone w jedną tablicę. szyk jest posortowanym wynikiem wejścia.

Program sortowania kubełkowego w C/C++

Wejście:

#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;
}

Wyjście:

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

Program sortowania kubełkowego w Python

Wejście:

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)

Wyjście:

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

Sortowanie wiadro Java

Wejście:

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 + " ");
        }
    }
}

Wyjście:

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

Zalety i wady sortowania wiaderkowego

Analiza złożoności sortowania wiaderkowego

Złożoność czasu sortowania wiadra

• Najlepsza złożoność przypadku: Jeśli wszystkie elementy tablicy są równomiernie rozłożone i wstępnie posortowane w każdym przedziale, rozproszenie elementów do odpowiednich przedziałów zajmuje O(n). Następnie sortowanie każdego przedziału za pomocą sortowanie przez wstawianie Kosztuje O(k). Zatem ogólna złożoność wynosi O(n+k).
• Średnia złożoność przypadku: W przypadku przypadków przeciętnych zakładamy, że dane wejściowe są równomiernie rozłożone. Zatem algorytm sortowania kubełkowego osiąga liniową złożoność czasową O(n+k). W tym przypadku rozproszenie elementów zajmuje czas O(n), a sortowanie ich metodą sortowania przez wstawianie zajmuje czas O(k).
• Najgorszy przypadek złożoności: W najgorszym przypadku elementy nie są równomiernie rozłożone i koncentrują się w jednym lub dwóch wiadrach. W takim przypadku sortowanie wiaderkowe degraduje się do zachowania podobnego do algorytm sortowania bąbelkowego. Dlatego w najgorszym przypadku złożoność czasowa sortowania kubełkowego wynosi O(n²).

Złożoność przestrzenna sortowania kubełkowego

Złożoność przestrzenna sortowania kubełkowego wynosi O(n*k). n to liczba elementów, a k to liczba kubełków potrzebnych do ich przechowywania podczas sortowania.

FAQ