Algoritmo de clasificación de depósitos (Java, Python, C/C++ Ejemplos de código)
sarah chen
¿Qué es la clasificación por cubos?
La clasificación por cubos, a menudo llamada clasificación por contenedores, es un método de clasificación por comparación que acepta una matriz sin clasificar como entrada y produce una matriz ordenada como resultado. Este método funciona distribuyendo los elementos en varios depósitos y clasificando cada uno de esos depósitos individualmente mediante cualquier algoritmo de clasificación, como la clasificación por inserción. Luego, todos los depósitos se fusionan para formar una matriz ordenada.
La clasificación por cubos se usa comúnmente cuando los elementos son:
- Valores de punto flotante
- Distribuida uniformemente en un rango
La complejidad temporal de la ordenación por cubos depende de la cantidad de cubos utilizados y de la uniformidad de la distribución de entrada. Si bien existen diferentes algoritmos de ordenación, como tipo de concha, ordenar por combinación, ordenar en montón y ordenación rápida puede lograr la complejidad de tiempo del mejor caso de O(n*logn), el algoritmo de ordenamiento de cubos puede lograr lo mismo en una complejidad de tiempo lineal u O(n).
La ordenación por contenedores sigue el método de dispersión-recolección. Al aplicar este método, los elementos se dispersan en los contenedores correspondientes, se ordenan en los contenedores y se reúnen para formar una matriz ordenada como paso final. Este método de dispersión-recolección se analiza en la siguiente sección.
Enfoque de dispersión-reunión
En ocasiones, los problemas complejos y de gran escala pueden resultar difíciles de resolver. El método de dispersión y recopilación intenta resolver dichos problemas dividiendo todo el conjunto de datos en grupos. Luego, se analiza cada grupo por separado y se vuelve a reunir todo para obtener la respuesta final.
Así es como el algoritmo de clasificación de depósitos implementa el método de dispersión y recolección:
Cómo funciona la clasificación de depósitos
El principio de funcionamiento básico de la clasificación de cubos es el siguiente:
- Se crea un conjunto de depósitos vacíos. Según las diferentes políticas, la cantidad de depósitos puede diferir.
- Desde la matriz de entrada, coloque cada elemento en su depósito correspondiente.
- Clasifique esos cubos individualmente.
- Concatene los depósitos ordenados para crear una única matriz de salida.
Los pasos de trabajo detallados se proporcionan en las siguientes secciones.
Pseudocó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 clasificación de depósitos para punto flotante Numbers
El algoritmo de ordenación de cubos para números de punto flotante dentro del rango de 0.0 a 1.0:
Paso 1) Cree diez (10) cubos vacíos de modo que el primer cubo contenga números dentro del rango [0.0, 0.1]. Luego, el segundo cubo contendrá dentro del rango [0.1, 0.2), y así sucesivamente.
Paso 2) Para cada elemento de la matriz:
-
a. Calcule el índice del depósito usando la fórmula:
índice de depósito = no_of_buckets *array_element
-
b. Inserte el elemento en el depósito[bucket_index]
Paso 3) Clasifique cada cubo individualmente usando la clasificación por inserción.
Paso 4) Concatene todos los depósitos en una sola matriz.
Veamos un ejemplo de ordenación por cubos. Para este ejemplo, ordenaremos la siguiente matriz utilizando el algoritmo de ordenación por cubos:
Paso 1) Primero, crearemos 10 contenedores vacíos. El primer contenedor contendrá los números entre [0.0, 0.1). Luego, el segundo contenedor contendrá los números entre [0.1, 0.2), y así sucesivamente.
Paso 2) Para cada elemento de la matriz, calcularemos el índice del depósito y colocaremos el elemento en ese depósito.
El índice del depósito se puede calcular mediante la fórmula:
índice_de_cubo= no_de_cubos*elemento_matriz
Cálculo del índice de cubeta:
a) 0.78
índice_de_cubo = no_de_cubos*elemento_matriz
* = 10 0.78
= 7.8
Por lo tanto, el elemento 0.78 se almacenará en el depósito [piso (7.8)] o en el depósito [7].
b) 0.17
bucket_index = no_of_buckets * elemento de matriz
* = 10 0.17
= 1.7
El elemento de matriz 0.17 se almacenará en el depósito [piso (1.7)] o en el depósito [1].
c) 0.39
bucket_index = no_of_buckets * elemento de matriz
= 10 * 0.39
= 3.9
0.39 se almacenará en el depósito [piso (3.9)] o en el depósito [3].
Después de iterar sobre todos los elementos de la matriz, los contenedores serán los siguientes:
Paso 3) Luego, cada contenedor se ordenará mediante ordenación por inserción. Después de la operación de ordenación, el resultado sería el siguiente:
Paso 4) En el paso final, los depósitos se concatenarán en una única matriz. Esa matriz será el resultado ordenado de la entrada.
Cada depósito se concatenará a la matriz de salida. Por ejemplo, la concatenación de los elementos del segundo depósito:
La concatenación de los últimos elementos del bucket será la siguiente:
Después de la concatenación, la matriz resultante será la matriz ordenada deseada.
Programa de clasificación de depósitos en 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;
}
Salida:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Programa de clasificación de cubos en 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))
Salida:
Sorted Output: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]
Ordenar en cubos 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]+" ");
}
}
}
Salida:
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 clasificación de depósitos para elementos enteros
El algoritmo de ordenamiento de cubos para la entrada que contiene números más allá del rango [0.0, 1.0] es un poco diferente al anterior. algoritmo. Los pasos requeridos para este caso son los siguientes:
Paso 1) Encuentra los elementos máximo y mínimo.
Paso 2) Seleccione la cantidad de depósitos, n, e inicialice esos depósitos como vacíos.
Paso 3) Calcule el rango o lapso de cada segmento usando la fórmula:
span = (maximum - minimum)/n
Paso 4) Para cada elemento de la matriz:
-
1.Calcular el índice del depósito:
bucket_index = (element - minimum)/span-
2.Inserte el elemento en el depósito[bucket_index]
Paso 5) Ordene cada depósito mediante ordenación por inserción.
Paso 6) Concatene todos los depósitos en una sola matriz.
Veamos un ejemplo de este algoritmo de ordenación por cubos. Para este ejemplo, ordenaremos la siguiente matriz utilizando el algoritmo de ordenación por cubos:
Paso 1) En el primer paso, es necesario encontrar los elementos máximo y mínimo de la matriz dada. Para este ejemplo, el máximo es 24 y el mínimo es 1.
Paso 2) Ahora tenemos que seleccionar una cantidad de depósitos vacíos, n. En este ejemplo, tomaremos 5 cubos. Luego los inicializaremos como vacíos.
Paso 3) La longitud de cada cubo debe calcularse mediante la siguiente fórmula:
span = (maximum-minimum)/n = (24-1)/5 = 4;
Por lo tanto, el primer grupo contendrá los números dentro del rango [0, 5). El segundo grupo contendrá los números dentro del rango [5, 10), y así sucesivamente.
Paso 4) Para cada elemento de la matriz, calcularemos el índice del depósito y colocaremos el elemento en ese depósito. El índice del depósito se puede calcular mediante la fórmula:
bucket_index = (element - minimum)/span
Cálculo del índice de cubeta:
-
a) 11bucket_index = (elemento – mínimo)/span
=(11-1)/4
=2
Por lo tanto, el elemento 11 se almacenará en el depósito [2].
-
b) 9
bucket_index = (elemento – mínimo)/span
=(9-1)/4
=2
Nota: Como 9 es un elemento límite para el depósito [1], debe agregarse en el depósito [1] en lugar de agregarlo en el mismo depósito del elemento anterior.
Luego de realizar las operaciones para cada elemento los buckets quedarán de la siguiente manera:
Paso 5) Ahora, cada depósito se ordenará mediante ordenación por inserción. Los cubos después de clasificar
Paso 6) En el paso final, los depósitos se concatenarán en una única matriz. Eso matriz será el resultado ordenado de la entrada.
Programa de clasificación de depósitos en 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;
}
Salida:
Sorted Output:1 8 9 11 12 13 17 19 21 24
Programa de clasificación de cubos en 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)
Salida:
Sorted Output: [1, 8, 9, 11, 12, 13, 17, 19, 21, 24]
Ordenar en cubos 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 + " ");
}
}
}
Salida:
Sorted Output: 1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0
Pros y Contras
| Ventajas | Contras |
|---|---|
| Realizar cálculos más rápidos | Consume más espacio en comparación con otros algoritmos. |
| Se puede utilizar como método de clasificación externo. | Funciona mal cuando los datos no están distribuidos uniformemente |
| Los cubos se pueden procesar de forma independiente |
Análisis de complejidad de clasificación por categorías
Complejidad temporal de la clasificación por cubos
- Mejora la complejidad del caso:Si todos los elementos de la matriz se distribuyen y clasifican uniformemente de antemano, se necesitaría O(n) tiempo para dispersar los elementos en los depósitos correspondientes. Luego clasifica cada cubo usando tipo de inserción costaría O(k). Por lo tanto, la complejidad total sería O(n+k).
- Complejidad media del caso:Para los casos promedio, asumimos que las entradas están distribuidas uniformemente. Por lo tanto, el algoritmo de ordenamiento por cubetas logra una complejidad temporal lineal de O(n+k). Aquí se requiere tiempo O(n) para dispersar los elementos y tiempo O(k) para ordenar esos elementos mediante ordenamiento por inserción.
- Complejidad del peor caso:En el peor de los casos, los elementos no estarán distribuidos uniformemente ni concentrados en uno o dos cubos específicos. En ese caso, la clasificación por depósitos funcionará como una Algoritmo de clasificación de burbujas. Por lo tanto, en el peor de los casos, la complejidad temporal de una ordenación por categorías sería O(n^2).
Complejidad espacial de la clasificación por cubos
La complejidad espacial de la ordenación por cubos es O(n*k). Aquí n es la cantidad de elementos y k es la cantidad de cubos necesarios.
