Algoritmo de clasificación de depósitos (Java, Python, C/C++ Code Ejemplos)

¿Qué es la clasificación por cubos?

El algoritmo de ordenación por cubetas, también conocido como ordenación por intervalos, es un método de ordenación por distribución basado en comparaciones que acepta un array sin ordenar como entrada y produce un array ordenado como salida. Esta técnica distribuye los elementos en varias cubetas y ordena cada cubeta individualmente mediante otro algoritmo de ordenación, como la ordenación por inserción. Finalmente, todas las cubetas se combinan para formar el array ordenado final.

El algoritmo Bucket Sort se usa comúnmente cuando los elementos son:

1. Valores de punto flotante
2. Distribuido uniformemente en un rango conocido

La complejidad temporal del algoritmo de ordenación por cubetas depende del número de cubetas utilizadas y de la uniformidad de la distribución de entrada. Mientras que otros algoritmos de ordenación, como tipo de concha, ordenar por combinación, ordenar en montón y ordenación rápida Si bien el algoritmo Bucket Sort logra una complejidad temporal en el mejor de los casos de O(n*logn), puede alcanzar una complejidad temporal lineal de O(n) en condiciones favorables.

El algoritmo de ordenación por cubetas sigue el método de dispersión-recolección. Los elementos se distribuyen en cubetas correspondientes, se ordenan dentro de cada cubeta y, como paso final, se agrupan para formar una matriz ordenada. Este método de dispersión-recolección se analiza en la siguiente sección.

Enfoque de dispersión y recolección

En ocasiones, los problemas complejos y de gran escala pueden resultar difíciles de resolver directamente. El método de dispersión-recopilación aborda estos problemas dividiendo el conjunto de datos completo en clústeres. Cada clúster se procesa por separado y los resultados se combinan para obtener la respuesta final.

Así es como el algoritmo de ordenación por cubetas implementa el método de dispersión-recolección:

Cómo funciona la clasificación de depósitos

El principio de funcionamiento básico del algoritmo de clasificación por cubetas es el siguiente:

1. Se crea un conjunto de cubetas vacías. Según la política elegida, el número de cubetas puede variar.
2. A partir del array de entrada, cada elemento se coloca en su cubo correspondiente.
3. Cada cubo se ordena individualmente mediante un algoritmo de ordenación secundario.
4. Los cubos ordenados se concatenan para producir una única matriz de salida.

Apodo 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 clasificación de depósitos para punto flotante Numbers

El algoritmo de ordenación por cubetas para números de punto flotante en el rango [0.0, 1.0]:

Paso 1) Crea diez (10) cubos vacíos. El primer cubo contiene números dentro del rango [0.0, 0.1). El segundo cubo contiene [0.1, 0.2), y así sucesivamente.

Paso 2) Para cada elemento de la matriz:

• a. Calcule el índice del cubo utilizando la fórmula:
  índice_cubeta = número_de_cubetas * elemento_de_matriz
• b. Inserta el elemento en bucket[bucket_index]

Paso 3) Clasifique cada cubo individualmente usando la clasificación por inserción.

Paso 4) Concatenar todos los cubos en una única matriz ordenada.

Veamos un ejemplo de ordenación por cubetas. Para este ejemplo, ordenaremos el siguiente array:

Paso 1) Primero, creamos 10 cubetas vacías. La primera cubeta contiene números en [0.0, 0.1). La segunda cubeta contiene [0.1, 0.2), y así sucesivamente.

Paso 2) Para cada elemento de la matriz, calcule el índice del cubo y coloque el elemento en ese cubo.

El índice de cubeta se calcula utilizando la fórmula:
        índice_cubeta = número_de_cubetas * elemento_de_matriz

Cálculo del índice de cubeta:
a) 0.78
      índice_cubeta = número_de_cubetas * elemento_de_matriz
              = 10 * 0.78
              = 7.8
Por lo tanto, el elemento 0.78 se almacena en bucket[floor(7.8)] o bucket[7].

b) 0.17
      índice_cubeta = número_de_cubetas * elemento_de_matriz
              = 10 * 0.17
              = 1.7

El elemento de matriz 0.17 se almacena en bucket[floor(1.7)] o bucket[1].

c) 0.39
      índice_cubeta = número_de_cubetas * elemento_de_matriz
              = 10 * 0.39
              = 3.9
0.39 se almacena en bucket[floor(3.9)] o bucket[3].

Tras iterar sobre todos los elementos del array, los cubos tienen el siguiente aspecto:

Paso 3) Cada cubo se ordena luego mediante el algoritmo de ordenación por inserción. Después de la operación de ordenación, el resultado es:

Paso 4) En el último paso, los cubos se concatenan en un único array. Ese array es el resultado ordenado de la entrada.

Cada cubo se concatena al array de salida. Por ejemplo, la concatenación de los elementos del segundo cubo:

La concatenación de los últimos elementos del bucket se muestra a continuación:

Tras la concatenación, el array resultante es el array ordenado deseado.

Programa de clasificación de depósitos en 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;
}

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

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 ordenación por cubetas para entradas que contienen números fuera del rango [0.0, 1.0] es ligeramente diferente del anterior. algoritmoLos pasos necesarios para este caso son los siguientes:

Paso 1) Encuentra los elementos máximo y mínimo del arreglo.

Paso 2) Seleccione el número de cubetas, n, e inicialícelas como vacías.

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 cubo:
          bucket_index = (element - minimum) / span
• 2. Inserta el elemento en bucket[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 cubetas. Para este ejemplo, ordenaremos el siguiente array:

Paso 1) En el primer paso, encontramos los elementos máximo y mínimo del arreglo dado. Para este ejemplo, el máximo es 24 y el mínimo es 1.

Paso 2) A continuación, seleccionamos el número de cubetas vacías, n. En este ejemplo, usamos 5 cubetas y las inicializamos como vacías.

Paso 3) El rango de cada cubo se calcula utilizando la fórmula:
        span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Por lo tanto, el primer cubo contiene números dentro del intervalo [0, 5). El segundo cubo contiene números dentro del intervalo [5, 10), y así sucesivamente.

Paso 4) Para cada elemento del array, calcula el índice del cubo y coloca el elemento en ese cubo. El índice del cubo se calcula utilizando la fórmula:
        bucket_index = (element - minimum) / span

Cálculo del índice de cubeta:

a) 11
bucket_index = (elemento – mínimo) / intervalo
        = (11 - 1) / 4
        = 2

Por lo tanto, el elemento 11 se almacena en el bucket[2].

b) 9
bucket_index = (elemento – mínimo) / intervalo
        = (9 - 1) / 4
        = 2

Nota: Como 9 es un elemento límite para bucket[1], se agrega a bucket[1] en lugar de colocarse en el mismo bucket que el elemento anterior.

Tras realizar las operaciones para cada elemento, los cubos quedan de la siguiente manera:

Paso 5) Ahora, cada cubo se ordena mediante el método de ordenación por inserción. Los cubos después de la ordenación:

Paso 6) En el paso final, los cubos se concatenan en una sola matriz. Eso matriz es 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=0; 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:
", 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

Ventajas y desventajas de la clasificación por cubetas

Análisis de complejidad de clasificación por categorías

Complejidad del tiempo de ordenamiento de cubos

• Mejora la complejidad del caso: Si todos los elementos del arreglo están distribuidos uniformemente y preordenados dentro de cada cubo, se requiere un tiempo O(n) para dispersar los elementos en los cubos correspondientes. Luego, ordenar cada cubo usando tipo de inserción Los costos son O(k). Por lo tanto, la complejidad general es O(n+k).
• Complejidad media del caso: En casos promedio, asumimos que las entradas están distribuidas uniformemente. Por lo tanto, el algoritmo de ordenación por cubetas alcanza una complejidad temporal lineal de O(n+k). Aquí, se requiere un tiempo de O(n) para dispersar los elementos y un tiempo de O(k) para ordenarlos mediante el algoritmo de ordenación por inserción.
• Complejidad del peor caso: En el peor de los casos, los elementos no están distribuidos uniformemente y se concentran en uno o dos cubos. En ese caso, Bucket Sort se degrada a un comportamiento similar a un algoritmo de ordenación de burbujaPor lo tanto, en el peor de los casos, la complejidad temporal de Bucket Sort es O(n²).

Complejidad espacial de la clasificación por cubos

La complejidad espacial del algoritmo de ordenación por cubetas es O(n*k). Aquí, n es el número de elementos y k es el número de cubetas necesarias para contenerlos durante la ordenación.

Preguntas Frecuentes