Algoritmo di ordinamento del bucket (Java, Python, C/C++ Code Esempi)

Cos'è l'ordinamento dei bucket?

L'ordinamento a bucket, spesso chiamato anche ordinamento a bin, è un metodo di ordinamento distribuito basato sul confronto che accetta un array non ordinato come input e produce un array ordinato come output. Questa tecnica distribuisce gli elementi in diversi bucket e ordina ciascun bucket individualmente utilizzando un altro algoritmo di ordinamento, come l'ordinamento per inserimento. Infine, tutti i bucket vengono uniti per formare l'array ordinato finale.

L'ordinamento a secchielli viene comunemente utilizzato quando gli elementi sono:

1. Valori in virgola mobile
2. Distribuito uniformemente su un intervallo noto

La complessità temporale del Bucket Sort dipende dal numero di bucket utilizzati e dall'uniformità della distribuzione di input. Mentre altri algoritmi di ordinamento come ordinamento della shell, unisci sort, heapsort e smistamento rapido Con una complessità temporale nel caso migliore pari a O(n*logn), l'algoritmo Bucket Sort può raggiungere una complessità temporale lineare O(n) in condizioni favorevoli.

L'algoritmo Bucket Sort segue l'approccio "disperdi e raccogli". Gli elementi vengono dispersi nei rispettivi bucket, ordinati all'interno di ciascun bucket e, come passaggio finale, raccolti per formare un array ordinato. Questo approccio "disperdi e raccogli" verrà discusso nella sezione successiva.

Approccio di dispersione e raccolta

I problemi complessi e su larga scala possono talvolta risultare difficili da risolvere direttamente. L'approccio "scatter-gather" affronta tali problemi suddividendo l'intero set di dati in cluster. Ciascun cluster viene elaborato separatamente e i risultati vengono poi combinati per produrre la risposta finale.

Ecco come l'algoritmo Bucket Sort implementa il metodo di dispersione e raccolta:

Come funziona l'ordinamento dei bucket

Il principio di funzionamento di base dell'algoritmo Bucket Sort è il seguente:

1. Viene creato un insieme di bucket vuoti. Il numero di bucket può variare a seconda della politica scelta.
2. Dall'array di input, ogni elemento viene inserito nel suo bucket corrispondente.
3. Ciascun bucket viene ordinato individualmente utilizzando un algoritmo di ordinamento secondario.
4. I bucket ordinati vengono concatenati per produrre un singolo array di output.

Soprannome 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

Metodo 1: algoritmo di ordinamento del bucket per virgola mobile Numbers

L'algoritmo Bucket Sort per numeri in virgola mobile nell'intervallo [0.0, 1.0]:

Passo 1) Crea dieci (10) secchi vuoti. Il primo secchio contiene i numeri compresi nell'intervallo [0.0, 0.1). Il secondo secchio contiene [0.1, 0.2), e così via.

Passo 2) Per ogni elemento dell'array:

• a. Calcola l'indice del bucket utilizzando la formula:
  indice_bucket = numero_di_bucket * elemento_array
• b. Inserire l'elemento nel bucket[bucket_index]

Passo 3) Ordina ciascun bucket individualmente utilizzando l'ordinamento per inserzione.

Passo 4) Unisci tutti i bucket in un unico array ordinato.

Analizziamo un esempio di Bucket Sort. In questo esempio, ordineremo il seguente array:

Passo 1) Innanzitutto, creiamo 10 bucket vuoti. Il primo bucket contiene i numeri in [0.0, 0.1). Il secondo bucket contiene [0.1, 0.2), e così via.

Passo 2) Per ogni elemento dell'array, calcola l'indice del bucket e inserisci l'elemento in quel bucket.

L'indice del bucket viene calcolato utilizzando la formula:
        indice_bucket = numero_di_bucket * elemento_array

Calcolo dell'indice del bucket:
a) 0.78
      indice_bucket = numero_di_bucket * elemento_array
              = 10 * 0.78
              = 7.8
Pertanto, l'elemento 0.78 viene memorizzato nel bucket[floor(7.8)] o nel bucket[7].

b) 0.17
      indice_bucket = numero_di_bucket * elemento_array
              = 10 * 0.17
              = 1.7

L'elemento dell'array 0.17 è memorizzato in bucket[floor(1.7)] o bucket[1].

c) 0.39
      indice_bucket = numero_di_bucket * elemento_array
              = 10 * 0.39
              = 3.9
0.39 è memorizzato nel bucket[floor(3.9)] o nel bucket[3].

Dopo aver iterato su tutti gli elementi dell'array, i bucket si presentano come segue:

Passo 3) Ciascun bucket viene quindi ordinato utilizzando l'algoritmo di ordinamento per inserimento. Dopo l'operazione di ordinamento, l'output è:

Passo 4) Nell'ultimo passaggio, i bucket vengono concatenati in un unico array. Tale array rappresenta il risultato ordinato dell'input.

Ciascun bucket viene concatenato all'array di output. Ad esempio, la concatenazione degli elementi del secondo bucket:

La concatenazione degli elementi dell'ultimo bucket è mostrata di seguito:

Dopo la concatenazione, l'array risultante è l'array ordinato desiderato.

Programma di ordinamento dei bucket in C/C++

Ingresso:

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

Produzione:

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

Programma di ordinamento del bucket in Python

Ingresso:

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

Produzione:

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

Ordinamento a secchiello Java

Ingresso:

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

Produzione:

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

Metodo 2: algoritmo di ordinamento del bucket per elementi interi

L'algoritmo Bucket Sort per input che contiene numeri al di fuori dell'intervallo [0.0, 1.0] è leggermente diverso dal precedente algoritmoI passaggi necessari in questo caso sono i seguenti:

Passo 1) Trova gli elementi massimi e minimi nell'array.

Passo 2) Seleziona il numero di bucket, n, e inizializzali come vuoti.

Passo 3) Calcola l'intervallo o l'intervallo di ciascun bucket utilizzando la formula:
        span = (maximum - minimum) / n

Passo 4) Per ogni elemento dell'array:

• 1. Calcola l'indice del bucket:
          bucket_index = (element - minimum) / span
• 2. Inserisci l'elemento nel bucket[bucket_index]

Passo 5) Ordina ciascun bucket utilizzando l'ordinamento per inserzione.

Passo 6) Concatena tutti i bucket in un unico array.

Analizziamo un esempio dell'algoritmo Bucket Sort. In questo esempio, ordineremo il seguente array:

Passo 1) Come primo passo, troviamo l'elemento massimo e quello minimo dell'array dato. In questo esempio, il massimo è 24 e il minimo è 1.

Passo 2) Successivamente, selezioniamo il numero di bucket vuoti, n. In questo esempio, utilizziamo 5 bucket e li inizializziamo come vuoti.

Passo 3) L'ampiezza di ciascun bucket viene calcolata utilizzando la formula:
        span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Pertanto, il primo contenitore contiene i numeri compresi tra [0, 5). Il secondo contenitore contiene i numeri compresi tra [5, 10), e così via.

Passo 4) Per ogni elemento dell'array, calcola l'indice del bucket e inserisci l'elemento in quel bucket. L'indice del bucket viene calcolato utilizzando la formula:
        bucket_index = (element - minimum) / span

Calcolo dell'indice del bucket:

a) 11
bucket_index = (elemento – minimo) / span
        = (11-1) / 4
        = 2

Pertanto, l'elemento 11 viene memorizzato nel bucket[2].

b) 9
bucket_index = (elemento – minimo) / span
        = (9-1) / 4
        = 2

Nota: Poiché 9 è un elemento di confine per bucket[1], viene aggiunto a bucket[1] invece di essere posizionato nello stesso bucket dell'elemento precedente.

Dopo aver eseguito le operazioni per ciascun elemento, i bucket si presentano come segue:

Passo 5) Ora, ogni bucket viene ordinato utilizzando l'algoritmo di ordinamento per inserimento. I bucket dopo l'ordinamento:

Passo 6) Nell'ultimo passaggio, i bucket vengono concatenati in un unico array. Questo schieramento è il risultato ordinato dell'input.

Programma di ordinamento dei bucket in C/C++

Ingresso:

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

Produzione:

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

Programma di ordinamento del bucket in Python

Ingresso:

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)

Produzione:

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

Ordinamento a secchiello Java

Ingresso:

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

Produzione:

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

Pro e contro del metodo di ordinamento a secchiello

Analisi della complessità del bucket sort

Complessità temporale dell'ordinamento a secchi

• migliore Complessità del caso: Se tutti gli elementi dell'array sono distribuiti uniformemente e preordinati all'interno di ciascun bucket, è necessario un tempo O(n) per spargere gli elementi nei bucket corrispondenti. Quindi l'ordinamento di ciascun bucket utilizzando ordinamento per inserzione Il costo è O(k). Pertanto, la complessità complessiva è O(n+k).
• Complessità media del caso: Nei casi medi, si assume che gli input siano distribuiti uniformemente. Pertanto, l'algoritmo Bucket Sort raggiunge una complessità temporale lineare di O(n+k). In questo caso, è necessario un tempo O(n) per la dispersione degli elementi e un tempo O(k) per ordinarli utilizzando l'ordinamento per inserimento.
• Complessità del caso peggiore: Nel caso peggiore, gli elementi non sono distribuiti uniformemente e si concentrano in uno o due bucket. In tal caso, il Bucket Sort si degrada in un comportamento simile a un algoritmo di ordinamento a bollePertanto, nel caso peggiore, la complessità temporale dell'algoritmo Bucket Sort è O(n²).

Complessità spaziale del bucket sort

La complessità spaziale dell'algoritmo Bucket Sort è O(n*k). Qui, n è il numero di elementi e k è il numero di bucket necessari per contenerli durante l'ordinamento.

DOMANDE FREQUENTI