Algoritmo de classificação de intervalo (Java, Python, C/C++ Exemplos de código)
Sarah Chen
O que é classificação de intervalo?
A classificação por balde, geralmente chamada de classificação por bin, é um método de classificação por comparação que aceita uma matriz não classificada como entrada e produz uma matriz classificada como resultado. Este método funciona distribuindo os elementos em vários baldes e classificando cada um desses baldes individualmente por qualquer algoritmo de classificação, como classificação por inserção. Em seguida, todos os buckets são mesclados para formar uma matriz classificada.
A classificação de balde é comumente usada quando os elementos são-
- Valores de ponto flutuante
- Distribuído uniformemente em um intervalo
A complexidade de tempo da classificação de bucket depende do número de buckets usados e da uniformidade da distribuição de entrada. Embora diferentes algoritmos de classificação, como classificar shell, mesclar classificação, heapsort e ordenação rápida pode atingir a complexidade de tempo do melhor caso de O (n * logn), o algoritmo de classificação de intervalo pode atingir o mesmo em complexidade de tempo linear ou O (n).
A classificação de balde segue a abordagem de coleta dispersa. Aplicando essa abordagem, os elementos são espalhados nos baldes correspondentes, classificados nos baldes e reunidos para formar uma matriz classificada como etapa final. Esta abordagem de coleta dispersa é discutida na seção seguinte
Abordagem de dispersão-reunião
Problemas complexos e de grande escala podem ocasionalmente ser difíceis de resolver. A abordagem scatter-gather tenta resolver tais problemas dividindo todo o conjunto de dados em clusters. Em seguida, cada cluster é abordado separadamente e reunido tudo para obter a resposta final.
É assim que o algoritmo de classificação de bucket implementa o método scatter-gather:
Como funciona a classificação de bucket
O princípio básico de funcionamento da classificação por balde é o seguinte:
- Um conjunto de buckets vazios é criado. Com base em políticas diferentes, o número de buckets pode ser diferente.
- Na matriz de entrada, coloque cada elemento em seu intervalo correspondente.
- Classifique esses buckets individualmente.
- Concatene os buckets classificados para criar uma única matriz de saída.
As etapas de trabalho detalhadas são fornecidas nas seções a seguir.
Pseudo-código
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 de classificação de intervalo para números de ponto flutuante no intervalo de 0.0 a 1.0:
Passo 1) Crie dez (10) baldes vazios de forma que o primeiro balde contenha números dentro do intervalo [0.0, 0.1). Então, o segundo intervalo conterá [0.1, 0.2) e assim por diante.
Passo 2) Para cada elemento da matriz:
-
a. Calcule o índice do balde usando a fórmula:
índice do balde= no_of_buckets *array_element
-
b. Insira o elemento no 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.
Vamos ver um exemplo de classificação por bucket. Para este exemplo, classificaremos o seguinte array usando o algoritmo de classificação de balde-
Passo 1) Primeiro, criaremos 10 baldes vazios. O primeiro intervalo conterá os números entre [0.0, 0.1). Em seguida, o segundo intervalo conterá os números entre [0.1, 0.2) e assim por diante.
Passo 2) Para cada elemento da matriz, calcularemos o índice do intervalo e colocaremos o elemento nesse intervalo.
O índice do bucket pode ser calculado usando a fórmula:
bucket_index= no_of_buckets*array_element
Cálculo do índice de intervalo:
a) 0.78
bucket_index = no_of_buckets*array_element
= 10 * 0.78
= 7.8
Portanto, o elemento 0.78 será armazenado no bucket[floor(7.8)] ou bucket[7].
b) 0.17
bucket_index = no_of_buckets * elemento da matriz
= 10 * 0.17
= 1.7
O elemento da matriz 0.17 será armazenado em bucket[floor(1.7)] ou bucket[1].
c) 0.39
bucket_index = no_of_buckets * elemento da matriz
= 10 * 0.39
= 3.9
0.39 será armazenado em bucket[floor(3.9)] ou bucket[3].
Depois de iterar todos os elementos do array, os intervalos serão os seguintes:
Passo 3) Em seguida, cada bucket será classificado usando classificação por inserção. Após a operação de classificação, a saída seria:
Passo 4) Na etapa final, os buckets serão concatenados em um único array. Essa matriz será o resultado classificado da entrada.
Cada bucket será concatenado ao array de saída. Por exemplo, a concatenação dos segundos elementos do bucket:
A concatenação dos últimos elementos do bucket será a seguinte:
Após a concatenação, o array resultante será o array ordenado desejado.
Programa de classificação de bucket em C/C++
Entrada:
//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;
}
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 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))
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 de classificação de intervalo para a entrada que contém números além do intervalo [0.0, 1.0] é um pouco diferente do anterior algoritmo. As etapas necessárias para este caso são as seguintes:
Passo 1) Encontre os elementos máximo e mínimo.
Passo 2) Selecione o número de buckets, n, e inicialize esses buckets 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.Calcular o índice do balde:
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 ver um exemplo desse algoritmo de classificação de bucket. Para este exemplo, classificaremos o seguinte array usando o algoritmo de classificação de balde-
Passo 1) Na primeira etapa, os elementos máximo e mínimo do array fornecido precisam ser encontrados. Para este exemplo, o máximo é 24 e o mínimo é 1.
Passo 2) Agora, temos que selecionar um número de baldes vazios, n. Neste exemplo, pegaremos 5 baldes. Então iremos inicializá-los como vazios.
Passo 3) A extensão de cada intervalo precisa ser calculada pela seguinte fórmula:
span = (maximum-minimum)/n = (24-1)/5 = 4;
Portanto, o primeiro intervalo conterá os números dentro do intervalo [0, 5). O segundo intervalo conterá os números entre [5, 10) e assim por diante.
Passo 4) Para cada elemento da matriz, calcularemos o índice do intervalo e colocaremos o elemento nesse intervalo. O índice do bucket pode ser calculado usando a fórmula:
bucket_index = (element - minimum)/span
Cálculo do índice de intervalo:
-
a) 11bucket_index = (elemento – mínimo)/span
=(11-1)/4
=2
Assim, o elemento 11 será armazenado no bucket[2].
-
b) 9
bucket_index = (elemento – mínimo)/span
=(9-1)/4
=2
Nota: Como 9 é um elemento de limite para o bucket[1], ele precisa ser anexado ao bucket[1] em vez de ser anexado ao mesmo bucket do elemento anterior.
Após realizar as operações para cada elemento, os buckets serão os seguintes:
Passo 5) Agora, cada bucket será classificado usando classificação por inserção. Os baldes após a classificação-
Passo 6) Na etapa final, os buckets serão concatenados em um único array. Que ordem será o resultado classificado 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; 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:\n", 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 & Contras
| Vantagens | Desvantagens |
|---|---|
| Execute cálculos mais rápidos | Consome mais espaço em comparação com outros algoritmos |
| Pode ser usado como um método de classificação externa | Apresenta desempenho ruim quando os dados não são distribuídos uniformemente |
| Os baldes podem ser processados de forma independente |
Análise de complexidade de classificação de intervalo
Complexidade de tempo da classificação do intervalo
- Melhor complexidade do caso:Se todos os elementos da matriz fossem uniformemente distribuídos e classificados de antemão, seria necessário tempo O(n) para espalhar os elementos nos compartimentos correspondentes. Em seguida, classificando cada balde usando tipo de inserção custaria O(k). Assim, a complexidade geral seria O(n+k).
- Complexidade média do caso:Para casos médios, assumimos que as entradas estão distribuídas uniformemente. Assim, o algoritmo de classificação de balde 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 classificar esses elementos usando a classificação por inserção.
- Complexidade do pior caso:Na pior das hipóteses, os elementos não serão distribuídos uniformemente e concentrados em um ou dois baldes específicos. Nesse caso, bucket sort funcionará como um algoritmo de classificação de bolhas. Portanto, no pior caso, a complexidade de tempo de uma classificação de intervalo seria O (n ^ 2).
Complexidade espacial da classificação de bucket
A complexidade do espaço da classificação de bucket é O(n*k). Aqui n é o número de elementos ek é o número de buckets necessários.
