0

Algorytm sortowania bąbelkowego – Strefa Juniora

Algorytm sortowania bąbelkowego

Algorytm sortowania bąbelkowego (Bubble Sort) jest pierwszym algorytmem, który przychodzi do głowy początkującym osobom jeżeli myślą o sortowaniu tablicy elementów. Nie jest on szczególnie wydajny, ale jest prosty w implementacji. Złożoność obliczeniowa algorytmu to O(n^2). Nie ma za to dużych narzutów pamięciowych (tylko O(1)). Czyli po ludzku: działa wolno, ale nie zjada dużo pamięci.

Jeżeli pojęcie złożoności obliczeniowej nie jest Ci znane, to możesz się z nim zapoznać np. tutaj. Najprościej mówiąc, jest to zasób (np. czas) potrzebny na rozwiązanie problemu (zakończenie się algorytmu) w zależności od ilości danych wejściowych. W tym przypadku złożoności O(n^2) oznacza, że jeżeli wykonanie algorytmu dla 10 elementów zajmuje 100 ms, to dla 100 elementów będzie to już 10 sec (10000 ms = 100 * 100), a dla 1000 elementów już 1000 sec. Jest to uproszczona definicja, w celu dokładnego zaznajomienia się z tym tematem polecam powyższy link. Jeżeli nie rozwiąże on Twoich wątpliwości, to daj znać w komentarzu, na pewno temu zaradzimy!
Artykuł ten stanowi wstęp 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.

Jak działa algorytm sortowania bąbelkowego?

Algorytm polega na porównywaniu dwóch elementów i ułożeniu ich według odpowiedniej kolejności (zgodnie z ich naturalnym porządkiem). Algorytm rozpoczyna na początku tablicy i zmierza ku końcowi. Sytuacja kiedy podczas całego przebiegu nie dokonano żadnej zmiany elementów oznacza, że cała tablica została posortowana. Pseudokod algorytmu można znaleźć min. https://pl.wikipedia.org/, więc nie będę się powtarzał ;).

Implementacja algorytmu sortowania bąbelkowego w C#

Od razu zaprezentuję implementację algorytmu w języku C#. Zaprezentuję dwie wersje implementacji. Na początek najprostszą (tak by każdy junior mógł szybko zrozumieć przykład), a później przerobię ją na uniwersalną implementację wykorzystującą obiekty IComparable. Dodatkowo w celach weryfikacji działania algorytmu napisałem proste testy jednostkowe.

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

Do prostej implementacji wykorzystam typ prosty tj. Int32. Kod prezentuje się następująco:

 public class SimpleBubbleSort
{
    public void Sort(int[] table)
    {
        for (int loop = 0; loop < table.Length - 1; ++loop)
        {
            for (int index = 0; index < table.Length - 1; ++index)
            {
                if (table[index] > table[index + 1])
                {
                    int temp = table[index];
                    table[index] = table[index + 1];
                    table[index + 1] = temp;
                }
            }
        }
    }
}

Algorytm przyjmuje tablice int[] i ją sortuje. Algorytm działa w dwóch pętlach, obie wykonują dokładnie tyle samo przebiegów z ilu elementów składa się tablica. W najgłębszej wykonuje się t zamiana elementów jeżeli ich kolejność się nie zgadza.

Algorytm ten można trochę poprawić tj. zmniejszyć mu złożoność obliczeniową. W najgorszym scenariuszu złożoność (tablica posortowana w odwrotnej kolejności) nadal wynosi O(n^2) jednak w realnych sytuacjach trochę ugramy. Zmiana polegała na dodaniu flagi, która informuje, czy w danym przebiegu została dokonana jakaś zamiana. Jeżeli takiej zmiany nie było, to można spokojnie zakończyć algorytm, gdyż elementy są posortowane. Poprawiony kod prezentuje się następująco:

public class SimpleBubbleSort
{
    public void Sort(int[] table)
    {
        bool swapped = false;
        for (int loop = 0; loop < table.Length - 1; ++loop)
        {
            for (int index = 0; index < table.Length - 1; ++index)
            {
                if (table[index] > table[index + 1])
                {
                    int temp = table[index];
                    table[index] = table[index + 1];
                    table[index + 1] = temp;
                    swapped = true;
                }
            }
            if (swapped == false)
            {
                break;
            }
        }
    }
}

Implementacja za pomocą interfejsu IComparable

W algorytmie opartym na tablicy obiektów IComparable zaimplementowałem od razu wersję z flagą:

public class BubbleSort
{
    public void Sort(IComparable[] table)
    {
        bool swapped = false;
        for (int loop = 0; loop < table.Length - 1; ++loop)
        {
            for (int index = 0; index < table.Length - 1; ++index)
            {
                if (table[index].CompareTo(table[index + 1]) > 0)
                {
                    IComparable temp = table[index];
                    table[index] = table[index + 1];
                    table[index + 1] = temp;
                    swapped = true;
                }
            }
            if (swapped == false)
            {
                break;
            }
        }
    }
}

Jedyna zmiana w stosunku do prostej wersji to taka, że przekazujemy tablicę obiektów IComparable. Przez to musiał zmienić się sposób porównywania obiektów. Implementacja interfejsu IComparable zakłada, że jeżeli wynik metody CompareTo jest większy od 0 to obiekt, na którym zostało wykonane porównanie znajduje się – w kolejności sortowania – za obiektem, z którym był porównywany. Dlatego też warunek if posiada teraz warunek table[index].CompareTo(table[index + 1]) > 0. Poza tymi zmianami reszta algorytmu nie uległa zmianie.

Testowanie algorytmu

Do testowania posłuży projekt testów jednostkowych.Przygotowałem dwa zestawy testowe, które mają za zadanie sprawdzić działanie algorytmu prostego oraz jeden zestaw do testów algorytmu opartego na IEnumerable. Dane w zestawach:

 

  • I
int[] SimpleExample1Input = new int[] { 8, 1, 10, 12, 11, 2, 6, 4, 3 };
int[] SimpleExample1Output = new int[] { 1, 2, 3, 4, 6, 8, 10, 11, 12 };
  • II
int[] SimpleExample2Input = new int[] { -12, 8, 1, 10, 12, 11, 2, 6, 4, 3, 0, 5, -4, -8 };
int[] SimpleExample2Output = new int[] { -12, -8, -4, 0, 1, 2, 3, 4, 5, 6, 8, 10, 11, 12 };
  • III
ComparableInt[] Example1Input = new ComparableInt[]
{
    new ComparableInt(-12), new ComparableInt(8), new ComparableInt(1),
    new ComparableInt(10), new ComparableInt(12), new ComparableInt(11),
    new ComparableInt(2), new ComparableInt(6), new ComparableInt(4),
    new ComparableInt(3), new ComparableInt(0), new ComparableInt(5),
    new ComparableInt(-4), new ComparableInt(-8), new ComparableInt(-24)
};
 
ComparableInt[] Example1Output = new ComparableInt[]
{
    new ComparableInt(-24), new ComparableInt(-12), new ComparableInt(-8),
    new ComparableInt(-4), new ComparableInt(0), new ComparableInt(1),
    new ComparableInt(2), new ComparableInt(3), new ComparableInt(4),
    new ComparableInt(5), new ComparableInt(6), new ComparableInt(8),
    new ComparableInt(10), new ComparableInt(11), new ComparableInt(12)
};

Jak widać na potrzeby testu została utworzona klasa ComparableInt, jej implementacja jest bardzo prosta. Ma na celu jedynie zaprezentowanie, że każdy implementujący interfejs Icomparable można posortować za pomocą naszego algorytmu. Kod klasy ComparableInt prezentuje się następująco:

public class ComparableInt : IComparable
{
    public int Value { get; private set; }
 
    public ComparableInt(int value)
    {
        Value = value;
    }
 
    public int CompareTo(object obj)
    {
        ComparableInt other = obj as ComparableInt;
        return Value.CompareTo(other.Value);
    }
}

Kod do testów algorytmu prostego wygląda następująco:

[TestMethod]
public void SimpleBubbleSort()
{
    SimpleBubbleSort bubble = new SimpleBubbleSort();
    int[] test1 = SortData.SimpleExample1Input;
    bubble.Sort(test1);
    Assert.IsTrue(Helpers.Equals(SortData.SimpleExample1Output, test1));
 
    int[] test2 = SortData.SimpleExample2Input;
    bubble.Sort(test2);
    Assert.IsTrue(Helpers.Equals(SortData.SimpleExample2Output, test2));
}

Z kolei kod do testów algorytmu generycznego prezentuje się tak:

[TestMethod]
public void BubbleSort()
{
    BubbleSort bubble = new BubbleSort();
    ComparableInt[] test1 = SortData.Example1Input;
    bubble.Sort(test1);
    Assert.IsTrue(Helpers.Equals(SortData.Example1Output, test1));
}

Na potrzeby testów napisałem metody pomocniczne, ich kod został wygląda następująco:

static class Helpers
{
    public static bool Equals(int[] tableA, int[] tableB)
    {
        if (tableA.Length != tableB.Length)
        {
            return false;
        }
        for (int index = 0; index < tableA.Length; index++)
        {
            if (tableA[index] != tableB[index])
            {
                return false;
            }
        }
        return true;
    }
 
    public static bool Equals(ComparableInt[] tableA, ComparableInt[] tableB)
    {
        if (tableA.Length != tableB.Length)
        {
            return false;
        }
        for (int index = 0; index < tableA.Length; index++)
        {
            if (tableA[index].Value != tableB[index].Value)
            {
                return false;
            }
        }
        return true;
    }
}

Oba testy wskazały wynik pozytywny. Algorytm działa prawidłowo.

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.