Bucket Sort

Sortowanie kubełkowe (Bucket Sort) to efektywny algorytm sortowania, który jest szczególnie skuteczny w przypadku równomiernie rozłożonych danych wejściowych. Działa poprzez podział zakresu wartości elementów wejściowych na pewną ilość kubełków, a następnie umieszczenie elementów w odpowiednich kubełkach na podstawie ich wartości. Kolejno sortuje zawartość każdego kubełka, a następnie scala kubełki, tworząc ostatecznie posortowaną kolekcję.

Oto ogólny opis algorytmu sortowania kubełkowego:

1. Ustal zakres wartości: Określ zakres wartości elementów w zbiorze wejściowym. Na podstawie tego zakresu podziel obszar wartości na odpowiednią liczbę kubełków.
2. Podział na kubełki: Stwórz odpowiednią ilość kubełków, zazwyczaj równą liczności zbioru wejściowego. Każdy kubełek jest przypisany do konkretnego zakresu wartości.
3. Rozłożenie elementów: Przechodź przez wszystkie elementy zbioru wejściowego i umieszczaj je w odpowiednich kubełkach na podstawie ich wartości. Wartości elementów w jednym kubełku muszą być mniejsze lub równe od zakresu tego kubełka.
4. Sortowanie kubełków: Dla każdego kubełka, który zawiera więcej niż jeden element, zastosuj inny algorytm sortowania. Na ogół używa się np. sortowania przez wstawianie lub quicksort.
5. Scalanie kubełków: Po posortowaniu kubełków, scala zawartość kubełków w jedną posortowaną kolekcję, zachowując odpowiednią kolejność.
6. Zakończenie: Po scaleniu kubełków otrzymujemy posortowany zbiór.

Algorytm ten jest szczególnie przydatny, gdy dane wejściowe są równomiernie rozłożone w zakresie wartości.
Jednak jego wydajność może spadać, gdy rozkład danych jest nierównomierny, ponieważ to wpływa na liczbę kubełków, które muszą być utworzone.

Warto zauważyć, że sortowanie kubełkowe jest przydatne w sytuacjach, gdzie zakres wartości jest ograniczony, na przykład sortowanie wyników egzaminów, ocen pracowników, itp.

Przykładowa implementacja

public interface IBucketSort
{
    List<int> Sort(List<int> inputList, int bucketCount);
}

public class BucketSortAlgorithm : IBucketSort
{
    public List<int> Sort(List<int> inputList, int bucketCount)
    {
        if (inputList.Count <= 1)
            return inputList;

        int minValue = inputList[0];
        int maxValue = inputList[0];

        for (int i = 1; i < inputList.Count; i++)
        {
            if (inputList[i] < minValue)
                minValue = inputList[i];
            else if (inputList[i] > maxValue)
                maxValue = inputList[i];
        }

        double range = (double)(maxValue - minValue + 1) / bucketCount;
        List<List<int>> buckets = new List<List<int>>(bucketCount);

        for (int i = 0; i < bucketCount; i++)
            buckets.Add(new List<int>());

        foreach (int num in inputList)
        {
            int bucketIndex = (int)((num - minValue) / range);
            buckets[bucketIndex].Add(num);
        }

        foreach (List<int> bucket in buckets)
        {
            if (bucket.Count > 1)
                InsertionSort(bucket);
        }

        List<int> sortedList = new List<int>(inputList.Count);
        foreach (List<int> bucket in buckets)
        {
            sortedList.AddRange(bucket);
        }

        return sortedList;
    }

    private void InsertionSort(List<int> list)
    {
        for (int i = 1; i < list.Count; i++)
        {
            int currentValue = list[i];
            int j = i - 1;

            while (j >= 0 && list[j] > currentValue)
            {
                list[j + 1] = list[j];
                j--;
            }

            list[j + 1] = currentValue;
        }
    }
}

Przykład użycia sortowania kubełkowego

public class BucketSort
{

    static void Main(string[] args)
    {
        List<int> numbers = new List<int> { 14, 35, 45, 17, 23, 56, 34, 47, 29, 11 };
        int bucketCount = 5;

        IBucketSort sorter = new BucketSortAlgorithm();
        List<int> sortedNumbers = sorter.Sort(numbers, bucketCount);

        Console.WriteLine("Posortowana lista:");
        foreach (int num in sortedNumbers)
        {
            Console.Write(num + " ");
        }
    }
}

Podczas implementacji algorytmu Bucket Sort warto zwrócić uwagę na kilka ważnych aspektów, aby zapewnić poprawność i wydajność kodu:

1. Wybór liczby kubełków: Odpowiedni wybór liczby kubełków jest kluczowy. Zbyt mała liczba kubełków może prowadzić do gorszej wydajności sortowania, szczególnie w przypadku niejednolitego rozkładu danych. Zbyt duża liczba kubełków może prowadzić do nadmiernego zużycia pamięci. Warto dostosować tę liczbę do charakterystyki danych wejściowych.
2. Zakres wartości: Znajdź zakres wartości elementów w zbiorze wejściowym, aby określić, jak szeroko podzielić kubełki. Błąd w określeniu zakresu może prowadzić do niepoprawnego rozłożenia elementów do kubełków.
3. Wybór algorytmu sortowania w kubełkach: Każdy kubełek, który zawiera więcej niż jeden element, musi być posortowany. Możesz wybrać odpowiedni algorytm sortowania do zastosowania wewnątrz kubełków, na przykład sortowanie przez wstawianie lub quicksort. Upewnij się, że wybrany algorytm jest efektywny.
4. Pamięć podręczna: Jeśli masz dostęp do pamięci podręcznej (np. na poziomie procesora)? Zastanów się nad optymalizacjami, które mogą poprawić wydajność dostępu do kubełków, szczególnie w przypadku dużych zbiorów danych.
5. Obsługa duplikatów: Jeśli dane wejściowe zawierają duplikaty, musisz zdecydować, jak je obsłużyć. Czy pozostawić duplikaty w jednym kubełku, czy traktować je jako osobne elementy?
6. Dostosowanie do typów nie liczbowych: Domyślnie Bucket Sort jest używany do sortowania liczb. Jeśli chcesz sortować nie liczbowe obiekty, musisz dostosować algorytm do porównywania tych obiektów.
7. Testowanie: Przetestuj algorytm na różnych zestawach danych, w tym na danych posortowanych, odwrotnie posortowanych i losowych, aby upewnić się, że działa poprawnie.
8. Zrozumienie złożoności: Pomimo że Bucket Sort jest efektywny w przypadku równomiernie rozłożonych danych. Złożoność czasowa może znacznie wzrosnąć w przypadku niejednolitego rozkładu danych. Zrozum, jakie są ograniczenia algorytmu w różnych przypadkach.
9. Kolejność wyników: Upewnij się, że wyniki sortowania są zgodne z oczekiwaniami. Może być konieczne dostosowanie kolejności sortowania (rosnącej lub malejącej) zależnie od wymagań.
10. Obsługa błędów: Zadbaj o obsługę przypadków błędów, takich jak próba sortowania pustej listy lub nieprawidłowy zakres kubełków.
11. Rozważ optymalizacje: W zależności od potrzeb projektu i charakterystyki danych, zastanów się nad optymalizacjami, które mogą poprawić wydajność algorytmu.

Bucket Sort jest najlepiej dostosowany do pewnych typów danych i rozkładów, dlatego warto zrozumieć, kiedy jest odpowiednim wyborem. A kiedy lepiej użyć innego algorytmu sortowania.