algorithm
Emmer sorteren

Emmersortering Basisinformatie

Bucket Sort is een sorteeralgoritme waarin elementen van de invoerarray in emmers worden verdeeld. Nadat alle elementen zijn verdeeld, worden emmers afzonderlijk gesorteerd met een ander sorteeralgoritme. Soms wordt het ook gesorteerd op recursieve methode.

Pseudo-code voor bucket-sortering

1. Laat n de lengte zijn van de invoerlijst L;
2. Voor elk element i van L
3. Als B [i] niet leeg is
4. Zet A [i] in B [i];
5. Anders B [i]: = A [i]
6. zet Concat B [i .. n] terug in één gesorteerde lijst;

Voorbeeld van bucket-sortering:

Meestal gebruiken mensen invoegingsparadigma voor een beetje optimalisatie.
Hulpruimte: O{n}

C # Implementatie

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;
    }
}