Clasificación de cubo

La ordenación de cubos es principalmente útil cuando la entrada se distribuye uniformemente en un rango. Por ejemplo, considere el siguiente problema. 
Ordene un gran conjunto de números de punto flotante que están en el rango de 0,0 a 1,0 y se distribuyen uniformemente en todo el rango. ¿Cómo ordenamos los números de manera eficiente?
Una forma sencilla es aplicar un algoritmo de clasificación basado en la comparación. El límite inferior para el algoritmo de clasificación basado en comparación (clasificación combinada, clasificación en montón, clasificación rápida, etc.) es Ω (n Log n), es decir, no pueden hacerlo mejor que nLogn. 
¿Podemos ordenar la array en tiempo lineal? La ordenación por conteo no se puede aplicar aquí ya que usamos claves como índice en la ordenación por conteo. Aquí las claves son números de punto flotante.  
La idea es usar la ordenación por cubos. El siguiente es el algoritmo del cubo.

bucketSort(arr[], n)
1) Create n empty buckets (Or lists).
2) Do following for every array element arr[i].
.......a) Insert arr[i] into bucket[n*array[i]]
3) Sort individual buckets using insertion sort.
4) Concatenate all sorted buckets.

Complejidad del tiempo: si asumimos que la inserción en un cubo toma un tiempo O(1), entonces los pasos 1 y 2 del algoritmo anterior claramente toman un tiempo O(n). El O(1) es fácilmente posible si usamos una lista enlazada para representar un depósito (en el siguiente código, el vector C++ se usa por simplicidad). El paso 4 también requiere tiempo O(n), ya que habrá n elementos en todos los cubos. 
El paso principal para analizar es el paso 3. Este paso también lleva tiempo O(n) en promedio si todos los números están distribuidos uniformemente (consulte el libro CLRS para obtener más detalles).
A continuación se muestra la implementación del algoritmo anterior.
 

// C++ program to sort an 
// array using bucket sort
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
  
// Function to sort arr[] of 
// size n using bucket sort
void bucketSort(float arr[], int n)
{
      
    // 1) Create n empty buckets
    vector<float> b[n];
  
    // 2) Put array elements 
    // in different buckets
    for (int i = 0; i < n; i++) {
        int bi = n * arr[i]; // Index in bucket
        b[bi].push_back(arr[i]);
    }
  
    // 3) Sort individual buckets
    for (int i = 0; i < n; i++)
        sort(b[i].begin(), b[i].end());
  
    // 4) Concatenate all buckets into arr[]
    int index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < b[i].size(); j++)
            arr[index++] = b[i][j];
}
  
/* Driver program to test above function */
int main()
{
    float arr[]
        = { 0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434 };
    int n = sizeof(arr) / sizeof(arr[0]);
    bucketSort(arr, n);
  
    cout << "Sorted array is \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

// Java program to sort an array
// using bucket sort
import java.util.*;
import java.util.Collections;
  
class GFG {
  
    // Function to sort arr[] of size n
    // using bucket sort
    static void bucketSort(float arr[], int n)
    {
        if (n <= 0)
            return;
  
        // 1) Create n empty buckets
        @SuppressWarnings("unchecked")
        Vector<Float>[] buckets = new Vector[n];
  
        for (int i = 0; i < n; i++) {
            buckets[i] = new Vector<Float>();
        }
  
        // 2) Put array elements in different buckets
        for (int i = 0; i < n; i++) {
            float idx = arr[i] * n;
            buckets[(int)idx].add(arr[i]);
        }
  
        // 3) Sort individual buckets
        for (int i = 0; i < n; i++) {
            Collections.sort(buckets[i]);
        }
  
        // 4) Concatenate all buckets into arr[]
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < buckets[i].size(); j++) {
                arr[index++] = buckets[i].get(j);
            }
        }
    }
  
    // Driver code
    public static void main(String args[])
    {
        float arr[] = { (float)0.897, (float)0.565,
                        (float)0.656, (float)0.1234,
                        (float)0.665, (float)0.3434 };
  
        int n = arr.length;
        bucketSort(arr, n);
  
        System.out.println("Sorted array is ");
        for (float el : arr) {
            System.out.print(el + " ");
        }
    }
}
  
// This code is contributed by Himangshu Shekhar Jha

# Python3 program to sort an array 
# using bucket sort 
def insertionSort(b):
    for i in range(1, len(b)):
        up = b[i]
        j = i - 1
        while j >= 0 and b[j] > up: 
            b[j + 1] = b[j]
            j -= 1
        b[j + 1] = up     
    return b     
              
def bucketSort(x):
    arr = []
    slot_num = 10 # 10 means 10 slots, each
                  # slot's size is 0.1
    for i in range(slot_num):
        arr.append([])
          
    # Put array elements in different buckets 
    for j in x:
        index_b = int(slot_num * j) 
        arr[index_b].append(j)
      
    # Sort individual buckets 
    for i in range(slot_num):
        arr[i] = insertionSort(arr[i])
          
    # concatenate the result
    k = 0
    for i in range(slot_num):
        for j in range(len(arr[i])):
            x[k] = arr[i][j]
            k += 1
    return x
  
# Driver Code
x = [0.897, 0.565, 0.656,
     0.1234, 0.665, 0.3434] 
print("Sorted Array is")
print(bucketSort(x))
  
# This code is contributed by
# Oneil Hsiao

// C# program to sort an array
// using bucket sort
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
  
  // Function to sort arr[] of size n
  // using bucket sort
  static void bucketSort(float []arr, int n)
  {
    if (n <= 0)
      return;
  
    // 1) Create n empty buckets
    List<float>[] buckets = new List<float>[n];
  
    for (int i = 0; i < n; i++) {
      buckets[i] = new List<float>();
    }
  
    // 2) Put array elements in different buckets
    for (int i = 0; i < n; i++) {
      float idx = arr[i] * n;
      buckets[(int)idx].Add(arr[i]);
    }
  
    // 3) Sort individual buckets
    for (int i = 0; i < n; i++) {
      buckets[i].Sort();
    }
  
    // 4) Concatenate all buckets into arr[]
    int index = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < buckets[i].Count; j++) {
        arr[index++] = buckets[i][j];
      }
    }
  }
  
  // Driver code
  public static void Main()
  {
    float []arr = { (float)0.897, (float)0.565,
                   (float)0.656, (float)0.1234,
                   (float)0.665, (float)0.3434 };
  
    int n = arr.Length;
    bucketSort(arr, n);
  
    Console.WriteLine("Sorted array is ");
    foreach(float el in arr) {
      Console.Write(el + " ");
    }
  }
}
  
// This code is contributed by rutvik_56

<script>
// Javascript program to sort an array
// using bucket sort
  
// Function to sort arr[] of size n
// using bucket sort
function bucketSort(arr,n)
{
    if (n <= 0)
            return;
   
        // 1) Create n empty buckets       
        let buckets = new Array(n);
   
        for (let i = 0; i < n; i++)
        {
            buckets[i] = [];
        }
   
        // 2) Put array elements in different buckets
        for (let i = 0; i < n; i++) {
            let idx = arr[i] * n;
            buckets[Math.floor(idx)].push(arr[i]);
        }
   
        // 3) Sort individual buckets
        for (let i = 0; i < n; i++) {
            buckets[i].sort(function(a,b){return a-b;});
        }
   
        // 4) Concatenate all buckets into arr[]
        let index = 0;
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < buckets[i].length; j++) {
                arr[index++] = buckets[i][j];
            }
        }
}
  
// Driver code
let arr = [0.897, 0.565,
         0.656, 0.1234,
         0.665, 0.3434];
let n = arr.length;
bucketSort(arr, n);
  
document.write("Sorted array is <br>");
for (let el of arr.values()) {
    document.write(el + " ");
}
  
// This code is contributed by unknown2108
</script>

Sorted array is 
0.1234 0.3434 0.565 0.656 0.665 0.897 

Algoritmo

1. Encuentre el elemento máximo y el mínimo de la array
2. Calcular el rango de cada cubeta

          range = (max - min) / n
          n is the number of buckets

        3. Crear n cubos de rango calculado

        4. Distribuya los elementos de la array en estos cubos

          BucketIndex = ( arr[i] - min ) / range

        5. Ahora ordena cada cubeta individualmente

        6. Reúna los elementos ordenados de los cubos en la array original

Input :    
Unsorted array:  [ 9.8 , 0.6 , 10.1 , 1.9 , 3.07 , 3.04 , 5.0 , 8.0 , 4.8 , 7.68 ]
No of buckets :  5

Output :  
Sorted array:   [ 0.6 , 1.9 , 3.04 , 3.07 , 4.8 , 5.0 , 7.68 , 8.0 , 9.8 , 10.1 ]

Input :    
Unsorted array:  [0.49 , 5.9 , 3.4 , 1.11 , 4.5 , 6.6 , 2.0]
No of buckets: 3

Output :  
Sorted array:   [0.49 , 1.11 , 2.0 , 3.4 , 4.5 , 5.9 , 6.6]

Código:

# Python program for the above approach
  
# Bucket sort for numbers 
# having integer part
def bucketSort(arr, noOfBuckets):
    max_ele = max(arr)
    min_ele = min(arr)
  
    # range(for buckets)
    rnge = (max_ele - min_ele) / noOfBuckets
  
    temp = []
  
    # create empty buckets
    for i in range(noOfBuckets):
        temp.append([])
  
    # scatter the array elements
    # into the correct bucket
    for i in range(len(arr)):
        diff = (arr[i] - min_ele) / rnge - 
              int((arr[i] - min_ele) / rnge)
  
        # append the boundary elements to the lower array
        if(diff == 0 and arr[i] != min_ele):
            temp[int((arr[i] - min_ele) / rnge) - 1].append(arr[i])
  
        else:
            temp[int((arr[i] - min_ele) / rnge)].append(arr[i])
  
    # Sort each bucket individually
    for i in range(len(temp)):
        if len(temp[i]) != 0:
            temp[i].sort()
  
    # Gather sorted elements 
    # to the original array
    k = 0
    for lst in temp:
        if lst:
            for i in lst:
                arr[k] = i
                k = k+1
  
  
# Driver Code
arr = [9.8, 0.6, 10.1, 1.9, 3.07, 3.04, 5.0, 8.0, 4.8, 7.68]
noOfBuckets = 5
bucketSort(arr, noOfBuckets)
print("Sorted array: ", arr)
  
# This code is contributed by
# Vinita Yadav

Sorted array:  [0.6, 1.9, 3.04, 3.07, 4.8, 5.0, 7.68, 8.0, 9.8, 10.1]

Bucket Sort Para ordenar una array con números negativos
Referencias:  
Introducción a los algoritmos 3.ª edición por Clifford Stein, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest  
http://en.wikipedia.org/wiki/Bucket_sort 
  
https:/ /youtu.be/VuXbEb5ywrU
Instantáneas: 

Cuestionario sobre clasificación de cubetas

Otros algoritmos de clasificación en GeeksforGeeks/GeeksQuiz: 

• Clasificación de selección
• Ordenamiento de burbuja
• Tipo de inserción
• Ordenar por fusión
• Ordenar montón
• Ordenación rápida
• Clasificación Radix
• Clasificación de conteo
• ShellOrdenar

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.