algorithm
Tipo de cubo

Bucket Sort Información Básica

La clasificación de cubo es un algoritmo de clasificación en el que los elementos de la matriz de entrada se distribuyen en grupos. Después de distribuir todos los elementos, los grupos se ordenan individualmente por otro algoritmo de clasificación. A veces también se ordena por método recursivo.

Pseudo código para Bucket Sort

1. Sea n la longitud de la lista de entrada L;
2. Para cada elemento i de L
3. Si B [i] no está vacío
4. Pon A [i] en B [i];
5. Else B [i]: = A [i]
6. devuelva el Concat B [i .. n] en una lista ordenada;

Ejemplo de clasificación de cubo:

En su mayoría, la gente usa el paradigma de inserción para un poco de optimización.
Espacio auxiliar: O{n}

Implementación de C #

public class BucketSort
{
    public static void SortBucket(ref int[] input)
    {
        int minValue = input[0];
        int maxValue = input[0];
        int k = 0;

        for (int i = input.Length - 1; i >= 1; i--)
        {
            if (input[i] > maxValue) maxValue = input[i];
            if (input[i] < minValue) minValue = input[i];
        }

        List<int>[] bucket = new List<int>[maxValue - minValue + 1];

        for (int i = bucket.Length - 1; i >= 0; i--)
        {
            bucket[i] = new List<int>();
        }

        foreach (int i in input)
        {
            bucket[i - minValue].Add(i);
        }

        foreach (List<int> b in bucket)
        {
            if (b.Count > 0)
            {
                foreach (int t in b)
                {
                    input[k] = t;
                    k++;
                }
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortBucket(ref input);
        return input;
    }
}