Algoritmul de sortare al găleților (Java, Python, C/C++ Code Exemple)

Ce este Bucket Sort?

Sortarea pe găleți, adesea numită sortare pe bin, este o metodă de sortare prin distribuție bazată pe comparație care acceptă o matrice nesortată ca intrare și produce o matrice sortată ca ieșire. Această tehnică distribuie elementele în mai multe găleți și sortează fiecare găleată individual folosind un alt algoritm de sortare, cum ar fi sortarea prin inserție. Apoi, toate gălețile sunt îmbinate pentru a forma matricea sortată finală.

Sortarea prin găleată este frecvent utilizată atunci când elementele sunt:

1. Valori în virgulă mobilă
2. Distribuit uniform pe un interval cunoscut

Complexitatea temporală a sortării pe găleți depinde de numărul de găleți utilizate și de uniformitatea distribuției intrării. În timp ce alți algoritmi de sortare, cum ar fi sortarea cochiliei, sortare îmbinare, sortare în grămada și sortare rapida Pentru a atinge o complexitate temporală optimă de O(n*logn), algoritmul de sortare prin bucket poate atinge o complexitate temporală liniară O(n) în condiții favorabile.

Sortarea în funcție de grup urmează metoda de sortare prin împrăștiere-adunare. Elementele sunt împrăștiate în grupări corespunzătoare, sortate în interiorul fiecărei grupări și adunate pentru a forma o matrice sortată ca pas final. Această metodă de sortare prin împrăștiere-adunare este discutată în secțiunea următoare.

Abordarea Scatter-Gather

Problemele complexe și de mare amploare pot fi uneori dificil de rezolvat direct. Abordarea de tip scatter-gather abordează astfel de probleme prin împărțirea întregului set de date în clustere. Fiecare cluster este procesat separat, iar rezultatele sunt reunite pentru a produce răspunsul final.

Iată cum implementează algoritmul Bucket Sort metoda scatter-gather:

Cum funcționează sortarea găleților

Principiul de bază al sortării prin găleată este următorul:

1. Se creează un set de compartimente goale. În funcție de politica aleasă, numărul de compartimente poate varia.
2. Din matricea de intrare, fiecare element este plasat în găleata corespunzătoare.
3. Fiecare găleată este sortată individual folosind un algoritm secundar de sortare.
4. Grupările sortate sunt concatenate pentru a produce o singură matrice de ieșire.

Pseudo 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: Algoritmul de sortare al găleților pentru virgulă mobilă Numbers

Algoritmul Bucket Sort pentru numere cu virgulă mobilă în intervalul [0.0, 1.0]:

Pas 1) Creați zece (10) compartimente goale. Prima compartimentă conține numere în intervalul [0.0, 0.1]. A doua compartimentă conține [0.1, 0.2] și așa mai departe.

Pas 2) Pentru fiecare element de matrice:

• a. Calculați indicele găleții folosind formula:
  index_bucket = nr_de_găleți * element_array
• b. Introduceți elementul în bucket[bucket_index]

Pas 3) Sortați fiecare găleată individual utilizând sortarea prin inserție.

Pas 4) Concatenează toate compartimentele într-o singură matrice sortată.

Să parcurgem un exemplu de sortare de tip „bucket sort”. Pentru acest exemplu, vom sorta următorul array:

Pas 1) Mai întâi, creăm 10 compartimente goale. Prima compartimentă conține numere între [0.0, 0.1]. A doua compartimentă conține [0.1, 0.2] și așa mai departe.

Pas 2) Pentru fiecare element al matricei, calculați indexul găleții și plasați elementul în găleata respectivă.

Indicele găleții se calculează folosind formula:
        index_bucket = nr_de_găleți * element_array

Calculul indicelui găleții:
a) 0.78
      index_bucket = nr_de_găleți * element_array
              = 10 * 0.78
              = 7.8
Prin urmare, elementul 0.78 este stocat în bucket[floor(7.8)] sau bucket[7].

b) 0.17
      index_bucket = nr_de_găleți * element_array
              = 10 * 0.17
              = 1.7

Elementul matricei 0.17 este stocat în bucket[floor(1.7)] sau bucket[1].

c) 0.39
      index_bucket = nr_de_găleți * element_array
              = 10 * 0.39
              = 3.9
0.39 este stocat în bucket[floor(3.9)] sau bucket[3].

După iterarea peste toate elementele matricei, compartimentele arată astfel:

Pas 3) Fiecare compartiment este apoi sortat folosind sortarea prin inserție. După operațiunea de sortare, rezultatul este:

Pas 4) În pasul final, compartimentele sunt concatenate într-o singură matrice. Matricea respectivă este rezultatul sortat al datelor de intrare.

Fiecare compartiment este concatenat cu matricea de ieșire. De exemplu, concatenarea elementelor celui de-al doilea compartiment:

Concatenarea ultimelor elemente ale găleții este prezentată mai jos:

După concatenare, matricea rezultată este matricea sortată dorită.

Program de sortare a găleților în C/C++

Intrare:

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

ieșire:

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

Programul de sortare a găleților în Python

Intrare:

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

ieșire:

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

Sortare cu găleată Java

Intrare:

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

ieșire:

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

Metoda 2: Algoritmul de sortare al găleților pentru elemente întregi

Algoritmul de sortare prin găleată pentru intrările care conțin numere dincolo de intervalul [0.0, 1.0] este ușor diferit de cel anterior AlgoritmulPașii necesari pentru acest caz sunt următorii:

Pas 1) Găsiți elementele maxime și minime din matrice.

Pas 2) Selectați numărul de găleți, n, și inițializați-le ca goale.

Pas 3) Calculați intervalul sau intervalul fiecărei găleți folosind formula:
        span = (maximum - minimum) / n

Pas 4) Pentru fiecare element de matrice:

• 1. Calculați indicele găleții:
          bucket_index = (element - minimum) / span
• 2. Introduceți elementul în bucket[bucket_index]

Pas 5) Sortați fiecare găleată folosind sortarea prin inserție.

Pas 6) Concatenează toate gălețile într-o singură matrice.

Să parcurgem un exemplu al acestui algoritm de sortare prin „Bucket Sort”. Pentru acest exemplu, vom sorta următorul array:

Pas 1) În primul pas, găsim elementele maxime și minime ale tabloului dat. Pentru acest exemplu, maximul este 24, iar minimul este 1.

Pas 2) Apoi, selectăm numărul de găleți goale, n. În acest exemplu, folosim 5 găleți și le inițializăm ca goale.

Pas 3) Deschiderea fiecărei cupe se calculează folosind formula:
        span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Prin urmare, prima categorie conține numere între [0, 5). A doua categorie conține [5, 10) și așa mai departe.

Pas 4) Pentru fiecare element al matricei, calculați indexul compartimentului și plasați elementul în compartimentul respectiv. Indexul compartimentului se calculează folosind formula:
        bucket_index = (element - minimum) / span

Calculul indicelui găleții:

a) 11
bucket_index = (element – ​​minim) / span
        = (11 - 1) / 4
        = 2

Astfel, elementul 11 ​​este stocat în găleata [2].

b) 9
bucket_index = (element – ​​minim) / span
        = (9 - 1) / 4
        = 2

Notă: Întrucât 9 este un element de delimitare pentru bucket[1], acesta este adăugat la bucket[1] în loc să fie plasat în același bucket ca elementul anterior.

După efectuarea operațiunilor pentru fiecare element, compartimentele arată astfel:

Pas 5) Acum, fiecare compartiment este sortat folosind sortarea prin inserție. Compartimentele după sortare:

Pas 6) În etapa finală, compartimentele sunt concatenate într-o singură matrice. Aceasta mulțime este rezultatul sortat al intrării.

Program de sortare a găleților în C/C++

Intrare:

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

ieșire:

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

Programul de sortare a găleților în Python

Intrare:

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)

ieșire:

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

Sortare cu găleată Java

Intrare:

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

ieșire:

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

Pro și contra sortării în funcție de găleată

Analiza complexității sortării găleții

Complexitatea timpului de sortare al găleții

• Complexitatea celui mai bun caz: Dacă toate elementele tabloului sunt distribuite uniform și pre-sortate în fiecare compartiment, este nevoie de un timp de O(n) pentru a împrăștia elementele în compartimentele corespunzătoare. Apoi, sortează fiecare compartiment folosind sortare inserție costă O(k). Prin urmare, complexitatea totală este O(n+k).
• Complexitatea medie a cazului: Pentru cazurile obișnuite, presupunem că intrările sunt distribuite uniform. Astfel, algoritmul Bucket Sort atinge o complexitate temporală liniară de O(n+k). Aici, este necesar un timp de O(n) pentru împrăștierea elementelor și un timp de O(k) pentru sortarea lor folosind sortarea prin inserție.
• Complexitatea celui mai rău caz: În cel mai rău caz, elementele nu sunt distribuite uniform și se concentrează într-una sau două găleți. În acest caz, sortarea pe găleți se degradează la un comportament similar cu o algoritmul de sortare cu bulePrin urmare, în cel mai rău caz, complexitatea temporală a sortării Bucket Sort este O(n²).

Complexitatea spațială a sortării găleții

Complexitatea spațială a sortării Bucket Sort este O(n*k). Aici, n este numărul de elemente, iar k este numărul de găleți necesare pentru a le conține în timpul sortării.

Întrebări frecvente