0

Algorytm sortowania kubełkowego – Strefa Juniora

Algorytm sortowania kubełkowego

Cześć! Dzisiaj poruszę przedostatni już algorytm z algorytmów sortowania tj. Algorytm sortowania kubełkowego (Bucket Sort). Algorytm ten jest kolejnym z tych, które napotykają na swojej drodze osoby rozpoczynające przygodę z algorytmami. Sortowanie kubełkowe jest szybsze (przy odpowiednich założeniach) od Insert Sort lub Bubble Sort. Złożoność obliczeniowa w najlepszym scenariuszu wynosi tylko O(n), pesymistyczny scenariusz – niestety – sortuje ze złożonością O(n^2). Optymistyczną złożoność osiągamy, jeżeli zbiór danych do sortowania ma rozkład jednostajny (co to oznacza wyjaśniam niżej).

Artykuł ten należy do cyklu przedstawiającego algorytmy rozwiązujące problem sortowania. Jeżeli temat Cię zainteresował, to koniecznie przeczytaj inne artykuły z tej tematyki, znajdziesz je w dziale algorytmów. Dodatkowo wpis ten zawiera informacje pomocne dla osoby zaczynającej swoją przygodę z programowaniem. Jeżeli jesteś taką osobą, to koniecznie odwiedź dział juniora.

Sposób działania sortowania kubełkowego

Działanie algorytmu (jak nazwa sugeruje ;)) opiera się na kubełkach. Ale co to są te kubełki? Są to pojemniki na sortowane elementy, logiczne, nie? Cała magia tych kubełków, polega na tym, że elementy w tych kubełkach powinny być z tej samej przestrzeni problemu. Przez przestrzeń rozumiem tutaj jakiś przedział, a przez problem, tablicę do posortowania. Czyli zakładając najprostszy scenariusz, dwa kubełki:

  • kubełek A – zawiera elementy z przedziału <min, (max-min)/2),
  • kubełek B – zawiera elementy z przedziału <(max-min)/2, max>.

Max i Min oznaczają kolejno: największy element zbioru, najmniejszy element zbioru. Teraz mając takie kubełki sortujemy elementy w kubełku A i doklejamy do tego posortowane elementy kubełka B. Jako wewnętrzny algorytm sortowania może posłużyć omawiany wcześniej np. bubble sort albo insert sort. Jest to o tyle szybsze, ponieważ przestrzeń problemu została podzielona na 2 przedziały, a z racji, że wewnętrzny algorytm ma zazwyczaj złożoność O(n^2), mając dwukrotnie mniejszy przedział, działa 4 razy szybciej. Idąc tym tokiem, dzieląc przedział na 10 kubełków zyskujemy przyspieszenie 100-krotne na algorytmach wewnętrznych, ale z racji, że trzeba je odpalić 10 razy, to finalnie algorytm ten działa 10 razy szybciej.

Przykład

Rozważ proszę prosty przykład w celu lepszego zrozumienia problemu. Załóżmy, że mamy do posortowania tablicę z 20 elementami:

{1,11,2,12,3,13,4,14,5,15,6,16,7,17,8,18,9,19,10,20}

I chcemy ją posortować za pomocą omawianego algorytmy sortowania kubełkowego. Liczbę kubełków ustalmy na 5. Działania jakie musisz podjąć:

  • Ustal ilość kubełków na 5.
  • Dla każdego kubełka określ zakres. Do obliczeń potrzebujesz jeszcze jednej wartości pivot. Pivot jest wartością co jaką będzie rozpoczynał się zakres kolejnego kubełka. Wylicz go ze wzoru:
    (max – min) / bucketsCount + 1
    (20 – 1) / 5 + 1 = 4

    Ten +1 wynika z tego, że dzieląc przez liczbę całkowite tracimy ułamkowa cześć. Przez to moglibyśmy źle rozdzielić kubełki, dodanie 1 do wyniku zapobiega wystąpieniu tego problemu.
  • Wylicz zakresy kubełków. W tym przykładzie będzie to:
    • A
      <1,4) // <min, pivot)
    • B
      <4,8) // <pivot, pivot *2)
    • C
      <8,12) // <pivot * 2, pivot *3)
    • D
      <12,16) // <pivot * 3, pivot *4)
    • E
      <16,20> // <pivot* 4, max>
  • Porozdzielaj liczby do kubełków:
    • 1 – A
    • 11 – C
    • 2 – A
    • 12 – D
    • 3 – A
    • 13 – D
    • itd…
  • Dla każdego kubełka zastosuj sortowanie.
  • Wypisz kolejny wyniki ze wszystkich kubełków. Wynik wygląda następująco:
    {0,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}

Analizując ten przykład mogłeś już się domyślić co oznacza wcześniej wspomniany rozkład jednostajny. Najprościej mówiąc oznacza on, że do każdego kubełka wpadnie podobna ilość elementów, że nie będzie kubełków pustych. Najgorszy z możłiwych scenariuszy, to taki, że do jednego kubełka wpadną prawie wszystkie elementy.

Implementacja algorytmu sortowania kubełkowego w C#

Kontynuując tradycję zapoczątkowaną w poprzednich wpisach musiałbym utworzyć dwie implementacje:

  • prostą – opartą o liczby całkowite,
  • uniwersalną – opartą na typach Icomparable.

Jednak z powodu natury tego algorytmu nie utworzę implementacji uniwersalnej. Utworzę implementację opartą na string i wytłumaczę dlaczego nie utworzyłem implementacji honorowanej wcześniej. Na samym końcu utworzę testy sprawdzające poprawność implementacji. Nie przedłużając, zacznijmy o prostej implementacji.

Cały kod użyty w tym przykładzie znajduje się również na GitHubie.
Kod napisany jest tak, aby był jak najbardziej czytelny. Oznacza to, że pominąłem wszelkie walidacje danych wejściowych. W kodzie produkcyjnym pamiętaj, aby zawsze upewniać się, że to co dostarcza Ci użytkownik ma prawidłowy format.

Prosta implementacja

Kod prostej implementacji prezentuje się następująco:

public class SimpleBucketSort
{
    private readonly int _bucketsCount;
 
    public SimpleBucketSort(int bucketsCount)
    {
        _bucketsCount = bucketsCount;
    }
 
    public void Sort(int[] table)
    {
        int min = table.Min();
        int max = table.Max();
        int pivot = (max - min) / _bucketsCount + 1;
        List<int>[] buckets = new List<int>[_bucketsCount];
        for (int i = 0; i < _bucketsCount; ++i)
        {
            buckets[i] = new List<int>();
        }
        foreach (int element in table)
        {
            int bucket = (element - min) / pivot;
            buckets[bucket].Add(element);
        }
        SimpleBubbleSort simpleBubble = new SimpleBubbleSort();
        List<int> sorted = new List<int>();
        foreach (List<int> bucket in buckets)
        {
            int[] toSort = bucket.ToArray();
            simpleBubble.Sort(toSort);
            sorted.AddRange(toSort);
        }
        for (int index = 0; index < table.Length; ++index)
        {
            table[index] = sorted[index];
        }
    }
}

Na początku w konstruktorze ustawiana jest wartość kubełków, a wartość ta jest zapisywana w zmiennej prywatnej. Sam algorytm można podzielić na kilka etapów:

  • przygotuj kubełki,
  • wypełnij kubełki,
  • posortuj kubełki,
  • przepisz kubełki do wyjścia.

Funkcja Sort jako pierwsza przygotowuje kubełki, tworzy tablicę kubełków i wypełnia tą tablicę kubełkami. Jest to pierwsza pętla for. W drugiej pętli tj. foreach, dane są rozdzielane po kubełkach. Indeks kubełka wyliczany jest za pomocą (element – min) / pivot, co dzięki dzieleniu bez reszty daje dokładny indeks kubełka, gdzie dane powinny trafić. Mając już dane w kubełkach, trzeba je posortować, do tego celu użyto wcześniej zaimplementowanego algorytmu Bubble Sort. Posortowane dane są na końcu przepisywane do wyjścia, robione jest to w ostatniej pętli, gdzie przepisywana jest wartość listy posortowanej. Użycie tutaj implementacji List<int> ma na celu uproszczenie implementacji, z nowych funkcji wykorzystałem tutaj jedynie .ToArray(), która przekształca listę do tablicy oraz .AddRange(…), która potrafi dodać do listy kolekcję elementów.

Implementacja sortująca stringi

W implementacji tej uporządkowałem trochę kod tak aby prezentował się bardziej profesjonalnie. Nadal jednak jest on na maksa uproszczony, mimo to z powodu natury algorytmu może wydawać się skomplikowany. Przejrzyj proszę kod, a później zapoznaj się z moim opisem:

Implementacja ta posiadaistotny defekt. Działa jedynie w przypadku słów zaczynających się od znaku z alfabetu o 25 znakach. Nie chciałem zbyt komplikować kodu, gdyż ma on na celu jedynie prezentację.
public class StringBucketSort
    {
        private readonly ISortAlgorithm _sortAlgorithm;
        private const int _bucketsCount = 26;

        public StringBucketSort(ISortAlgorithm sortAlgorithm)
        {
            _sortAlgorithm = sortAlgorithm;
        }

        public void Sort(string[] table)
        {
            List[] buckets = PrepareBuckets();
            PutToBuckets(buckets, table);
            List sorted = SortBuckets(buckets);
            for (int index = 0; index < table.Length; ++index)
            {
                table[index] = sorted[index];
            }
        }

        private List[] PrepareBuckets()
        {
            List[] buckets = new List[_bucketsCount];
            for (int i = 0; i < _bucketsCount; ++i)
            {
                buckets[i] = new List();
            }
            return buckets;
        }

        private void PutToBuckets(List[] buckets, string[] table)
        {
            foreach (string str in table)
            {
                int bucket = (int)str.ToUpper()[0] - 65;
                buckets[bucket].Add(str);
            }
        }

        private List SortBuckets(List[] buckets)
        {
            List sorted = new List();
            foreach (List bucket in buckets)
            {
                string[] toSort = bucket.ToArray();
                _sortAlgorithm.Sort(toSort);
                sorted.AddRange(toSort);
            }
            return sorted;
        }
    }

Zacznijmy może od konstruktora. Przyjmuje on implementację interfejsu ISortAlgorithm, aby można było przez DI (Dependency Injection) wstrzyknąć dowolną implementację algorytmu. Wszystkie poprzednio zaimplementowane algorytmy implementują ten interfejs. Następna różnicą jest usunięcie liczby definiującej ilość kubełków. Wartość ta jest na stałe ustawiona na 26 (liczba liter alfabetu). Dlaczego? O tym później. Przechodząc do funkcji sort, jej kod został zrefaktoryzowany. Rozbiłem poszczególne bloki operacji na osobne funkcje. Przeanalizujmy kolejno te funkcje.

Funkcji PrepareBuckets nie trzeba chyba zbytnio omawiać, przygotowuje ona kubełki. Cała magia i problem zamieszczone są w funkcji PutToBuckets, która umieszcza każdy element w jakimś kubełku. Tutaj objawia się problem, o którym pisałem, a mianowicie „Jak wyznaczyć numer kubełka?”. W przypadku int sprawa była prosta. W przypadku string jest trudniejsza, nie można po prostu skorzystać ze wzoru (max-min)/bucketsCount + 1, bo jak sprowadzić string do wartości liczbowych? Albo jeszcze lepiej: jak sprowadzić IComparable do wartości liczbowych? Nie da się tego łatwo zrobić, każdy typ ma inne sortowanie i sprawdzenie tego typu do wartości liczbowych mija się z celem. Do każdego typu trzeba tutaj podejść indywidualnie. Dlatego też prezentuje tutaj tylko implementację dla string. W przypadku string przyjąłem założenie, że liczba kubełków będzie wynosiła 26, a na indeks kubełka będzie wskazywała pierwsza litera słowa (oczywiście nie działa to dla znaków spoza podstawowego alfabetu – patrz uwaga wcześniej). Pierwszą literę słowa zamieniam na dużą, konwertuje na inta i odejmuje 65: int bucket = (int)str.ToUpper()[0] – 65. Czemu tak? A bo w kodzie ASCII litera A (duże A) ma wartość 65, więc aby sprowadzić liczby do indeksu 0, muszę odjąć tą wartość. Po umieszczeniu już elementów w kubełkach, sortuje je w funkcji SortBuckets za pomocą wstrzykniętego algorytmu. Następnie przepisuje wszystko do tablicy wyjściowej.

Testowanie algorytmu

W celu przetestowania algorytmu napisałem dwa proste UnitTesty. W jednym skorzystałem z wcześniej przygotowanych danych (pisałem o tym np. tu), a w drugim (tym testującym implementację dla string) przygotowałem zupełnie nowy zestaw:

public static string[] Example1StringsInput = new string[]
{
    "Warszawa","Jelenia Góra","Wrocław","Kraków","Opole","Poznań","Gdańsk","Barczewo","Bobowa", "Bukowiec","Kostrzyca","Kowary"
};
 
public static string[] Example1StringsOutput = new string[]
{
    "Barczewo","Bobowa", "Bukowiec","Gdańsk","Jelenia Góra","Kostrzyca","Kowary","Kraków","Opole","Poznań","Warszawa","Wrocław",
};

Kod testujący wygląda następująco:

[TestMethod]
public void SimpleBucketSort()
{
    SimpleBucketSort sort = new SimpleBucketSort(4);
    int[] test1 = SortData.SimpleExample1Input;
    sort.Sort(test1);
    Assert.IsTrue(Helpers.Equals(SortData.SimpleExample1Output, test1));
 
    int[] test2 = SortData.SimpleExample2Input;
    sort.Sort(test2);
    Assert.IsTrue(Helpers.Equals(SortData.SimpleExample2Output, test2));
}
 
[TestMethod]
public void StringBucketSort()
{
    StringBucketSort sort = new StringBucketSort(new BubbleSort());
    string[] test = SortData.Example1StringsInput;
    sort.Sort(test);
    for (int index = 0; index < SortData.Example1StringsOutput.Length; index++)
    {
        Assert.AreEqual(SortData.Example1StringsOutput[index], test[index]);
    }
}

Wszystkie testy przechodzą na zielono, co oznacza, że nasz algorytm został poprawnie zaimplementowany.

Podsumowanie

Jak widzisz, algorytm ten nie jest tak prosty w implementacji, jak poprzednio przedstawione. Przedstawiłem najprostszą implementacje dla string, która działa w bardzo okrojonym zakresie. Możesz popracować nad implementacją, która obsłuży wszystkie znaki, na pewnoe wyjdzie Ci to na dobre, chociaż z drugiej strony, po co? Algorytm QuickSort jest lepszy i na pewno łatwiejszy w implementacji ;). Tym też zajmę się w następnym wpisie, do którego przeczytania Cię zapraszam.

Pozdro!

Patryk Bogdański

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

This site uses Akismet to reduce spam. Learn how your comment data is processed.