Algoritmo de classificação de intervalo (Java, Python, C/C++ Code Exemplos)

O que é classificação de intervalo?

O Bucket Sort, também chamado de bin sort, é um método de ordenação por distribuição baseado em comparação que recebe um array não ordenado como entrada e produz um array ordenado como saída. Essa técnica distribui os elementos em vários buckets e ordena cada bucket individualmente usando outro algoritmo de ordenação, como o Insertion Sort. Em seguida, todos os buckets são mesclados para formar o array ordenado final.

O Bucket Sort é comumente usado quando os elementos são:

1. Valores de ponto flutuante
2. Distribuído uniformemente em uma faixa conhecida

A complexidade temporal do Bucket Sort depende do número de buckets utilizados e da uniformidade da distribuição de entrada. Enquanto outros algoritmos de ordenação, como... classificar shell, mesclar classificação, heapsort e ordenação rápida Para atingir uma complexidade de tempo no melhor caso de O(n*logn), o algoritmo Bucket Sort pode alcançar uma complexidade de tempo linear de O(n) em condições favoráveis.

O Bucket Sort segue a abordagem de dispersão e coleta. Os elementos são dispersos em baldes correspondentes, ordenados dentro de cada balde e, na etapa final, reunidos para formar um array ordenado. Essa abordagem de dispersão e coleta é discutida na seção seguinte.

Abordagem de dispersão e coleta

Problemas complexos e de grande escala podem, ocasionalmente, ser difíceis de resolver diretamente. A abordagem de dispersão e coleta resolve esses problemas dividindo todo o conjunto de dados em clusters. Cada cluster é processado separadamente e os resultados são reunidos para produzir a resposta final.

Eis como o algoritmo Bucket Sort implementa o método scatter-gather:

Como funciona a classificação de bucket

O princípio básico de funcionamento do Bucket Sort é o seguinte:

1. É criado um conjunto de buckets vazios. Dependendo da política escolhida, o número de buckets pode variar.
2. A partir da matriz de entrada, cada elemento é colocado em seu respectivo compartimento.
3. Cada compartimento é classificado individualmente usando um algoritmo de classificação secundário.
4. Os buckets ordenados são concatenados para produzir uma única matriz de saída.

Apelido 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

Método 1: Algoritmo de classificação de intervalo para ponto flutuante Numbers

O algoritmo Bucket Sort para números de ponto flutuante no intervalo [0.0, 1.0]:

Passo 1) Crie dez (10) baldes vazios. O primeiro balde contém números no intervalo [0.0, 0.1). O segundo balde contém [0.1, 0.2), e assim por diante.

Passo 2) Para cada elemento da matriz:

• a. Calcule o índice de bucket usando a fórmula:
  índice_do_bucket = número_de_buckets * elemento_do_array
• b. Insira o elemento em bucket[bucket_index]

Passo 3) Classifique cada bucket individualmente usando classificação por inserção.

Passo 4) Concatene todos os buckets em um único array ordenado.

Vamos analisar um exemplo de ordenação por balde (Bucket Sort). Neste exemplo, vamos ordenar o seguinte array:

Passo 1) Primeiro, criamos 10 baldes vazios. O primeiro balde contém números no intervalo [0.0, 0.1). O segundo balde contém números no intervalo [0.1, 0.2), e assim por diante.

Passo 2) Para cada elemento da matriz, calcule o índice do bucket e coloque o elemento nesse bucket.

O índice de bucket é calculado usando a fórmula:
        índice_do_bucket = número_de_buckets * elemento_do_array

Cálculo do índice de intervalo:
a) 0.78
      índice_do_bucket = número_de_buckets * elemento_do_array
              = 10 * 0.78
              = 7.8
Portanto, o elemento 0.78 é armazenado em bucket[floor(7.8)] ou bucket[7].

b) 0.17
      índice_do_bucket = número_de_buckets * elemento_do_array
              = 10 * 0.17
              = 1.7

O elemento 0.17 do array é armazenado em bucket[floor(1.7)] ou bucket[1].

c) 0.39
      índice_do_bucket = número_de_buckets * elemento_do_array
              = 10 * 0.39
              = 3.9
0.39 está armazenado em bucket[floor(3.9)] ou bucket[3].

Após percorrer todos os elementos da matriz, os buckets ficam assim:

Passo 3) Em seguida, cada bucket é ordenado usando o algoritmo de ordenação por inserção. Após a operação de ordenação, a saída é:

Passo 4) Na etapa final, os buckets são concatenados em um único array. Esse array representa o resultado ordenado da entrada.

Cada elemento do segundo bucket é concatenado ao array de saída. Por exemplo, a concatenação dos elementos do segundo bucket é a seguinte:

A concatenação dos últimos elementos do bucket é mostrada abaixo:

Após a concatenação, o array resultante é o array ordenado desejado.

Programa de classificação de bucket em C/C++

Entrada:

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

Saída:

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

Programa de classificação de bucket em Python

Entrada:

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

Saída:

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

Classificação do intervalo Java

Entrada:

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

Saída:

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

Método 2: Algoritmo de classificação de intervalo para elementos inteiros

O algoritmo Bucket Sort para entradas que contêm números fora do intervalo [0.0, 1.0] é ligeiramente diferente do anterior. algoritmoOs passos necessários para este caso são os seguintes:

Passo 1) Encontre os elementos máximo e mínimo na matriz.

Passo 2) Selecione o número de baldes, n, e inicialize-os como vazios.

Passo 3) Calcule o intervalo ou extensão de cada intervalo usando a fórmula:
        span = (maximum - minimum) / n

Passo 4) Para cada elemento da matriz:

• 1. Calcule o índice do bucket:
          bucket_index = (element - minimum) / span
• 2. Insira o elemento no bucket[bucket_index]

Passo 5) Classifique cada bucket usando classificação por inserção.

Passo 6) Concatene todos os buckets em um único array.

Vamos analisar um exemplo do algoritmo Bucket Sort. Neste exemplo, vamos ordenar o seguinte array:

Passo 1) No primeiro passo, encontramos os elementos máximo e mínimo da matriz fornecida. Para este exemplo, o máximo é 24 e o mínimo é 1.

Passo 2) Em seguida, selecionamos o número de baldes vazios, n. Neste exemplo, usamos 5 baldes e os inicializamos como vazios.

Passo 3) A duração de cada intervalo é calculada usando a fórmula:
        span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Portanto, o primeiro balde contém números no intervalo [0, 5). O segundo balde contém números no intervalo [5, 10), e assim por diante.

Passo 4) Para cada elemento da matriz, calcule o índice do bucket e coloque o elemento nesse bucket. O índice do bucket é calculado usando a fórmula:
        bucket_index = (element - minimum) / span

Cálculo do índice de intervalo:

a) 11
índice_do_balde = (elemento – mínimo) / span
        = (11 - 1) / 4
        = 2

Assim, o elemento 11 é armazenado no bucket[2].

b) 9
índice_do_balde = (elemento – mínimo) / span
        = (9 - 1) / 4
        = 2

Observação: Como 9 é um elemento limite para bucket[1], ele é anexado a bucket[1] em vez de ser colocado no mesmo bucket que o elemento anterior.

Após a execução das operações para cada elemento, os buckets ficam da seguinte forma:

Passo 5) Agora, cada bucket é ordenado usando o método de ordenação por inserção. Os buckets após a ordenação são:

Passo 6) Na etapa final, os buckets são concatenados em um único array. Isso ordem é o resultado ordenado da entrada.

Programa de classificação de bucket em C/C++

Entrada:

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

Saída:

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

Programa de classificação de bucket em Python

Entrada:

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)

Saída:

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

Classificação do intervalo Java

Entrada:

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

Saída:

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

Prós e contras da classificação por balde

Análise de complexidade de classificação de intervalo

Complexidade de tempo do Bucket Sort

• Melhor complexidade do caso: Se todos os elementos da matriz estiverem uniformemente distribuídos e pré-ordenados em cada bucket, será necessário um tempo O(n) para espalhar os elementos nos buckets correspondentes. Em seguida, a ordenação de cada bucket será feita usando... tipo de inserção custa O(k). Portanto, a complexidade geral é O(n+k).
• Complexidade média do caso: Para casos médios, assumimos que as entradas são distribuídas uniformemente. Assim, o algoritmo Bucket Sort atinge uma complexidade de tempo linear de O(n+k). Aqui, o tempo O(n) é necessário para espalhar os elementos e o tempo O(k) é necessário para ordená-los usando o algoritmo de ordenação por inserção.
• Complexidade do pior caso: No pior caso, os elementos não estão distribuídos uniformemente e se concentram em um ou dois buckets. Nesse caso, o Bucket Sort se degrada para um comportamento semelhante ao de um algoritmo de ordenação por blocos (Bucket Sort). algoritmo de classificação por bolhaPortanto, no pior caso, a complexidade de tempo do Bucket Sort é O(n²).

Complexidade espacial da classificação de bucket

A complexidade espacial do Bucket Sort é O(n*k). Aqui, n é o número de elementos e k é o número de buckets necessários para armazená-los durante a ordenação.

Perguntas Frequentes