0

Algorytm sortowania przez wstawienie – Strefa Juniora

Algorytm sortowania przez wstawienie

Algorytm sortowania przez wstawienie (Insertion Sort) jest jednym z najprostszych algorytmów sortowania (zaraz obok Bubble Sort). Jest on dosyć intuicyjny, ponieważ odzwierciedla działanie człowieka podczas np. sortowania talii kart. Złożoność obliczeniowa algorytmu wynosi O(n^2), więc jest on mało wydajny, jednak sprawuje się on trochę lepiej na tablicy już częściowo posortowanej.

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.

Jak działa algorytm sortowania przez wstawienie?

Działanie algorytmu opiera się na dwóch zbiorach: posortowanym i nieposortowanym. Na samym początku zbiór posortowany jest pusty, a zbiór nieposortowany jest tożsamy z danymi wejściowymi. W każdej iteracji algorytm wybiera element (zazwyczaj w kolejności jakiej przyszły) ze zbioru nieposortowanego i wstawia go do zbioru posortowanego. Pozycja gdzie wstawić element w zbiorze posortowanym podejmowana jest na podstawie porównań elementów. Porównuje się każdy element w zbiorze posortowanym i jeżeli aktualnie wyjęty element ze zbioru nieposortowanego jest <= z porównywanym, to wstawia się ten element w to miejsce. Algorytm kończy się w momencie, jeżeli zbiór nieposortowany nie zawiera już elementów. Opis może być trochę zagmatwany, ale sam schemat jest bardzo prosty. Przeanalizuj proszę przykład dla takiego zbioru liczb:

INPUT = {1, 5, 3, 2, 4}
  1. Utwórz zbiór posortowany OUTPUT (jest on pusty).
  2. Pobierz element ze zbioru INPUT. Element to ‘1’, z racji, że zbiór OUTPUT jest pusty, to wstawiasz go na pierwszą pozycję.
    INPUT = {5,3,2,4}
    OUTPUT = {1}
  3. Pobierz element ze zbioru INPUT. Element to ‘5’. Porównujesz ten element kolejno z elementami zbioru OUTPUT:
    1. porównujesz ‘1’ z ‘5’. ‘5’ jest większe niż ‘1’, więc nic nie zmieniasz,
    2. dotarłeś do końca zbioru więc wstawiasz element.

    Zbiory wyglądają następująco:

    INPUT = {3,2,4}
    OUTPUT = {1,5}
  4. Pobierz element ze zbioru INPUT. Element to ‘3’. Porównujesz ten element kolejno z elementami zbioru OUTPUT:
    1. porównujesz ‘1’ z ‘3’. ‘3’ jest większe niż ‘1’, więc nic nie zmieniasz,
    2. porównujesz ‘5’ z ‘3’. ‘5’ jest większe niż ‘3’, więc wstawiasz ‘3’ na aktualnym indeksie tablic tj. [1] (pamiętamy, że jak prawdziwi programiści liczymy od 0 ;)?).

    Zbiory wyglądają następująco:

    INPUT = {2,4}
    OUTPUT = {1,3,5}
  5. Pobierz element ze zbioru INPUT. Element to ‘2’. Porównujesz ten element kolejno z elementami zbioru OUTPUT:
    1. porównujesz ‘1’ z ‘2’. ‘2’ jest większe niż ‘1’, więc nic nie zmieniasz,
    2. porównujesz ‘3’ z ‘2’. ‘3’ jest większe niż ‘2’, więc wstawiasz ‘2’ na aktualnym indeksie tablic tj. [1].

    Zbiory wyglądają następująco:

    INPUT = {4}
    OUTPUT = {1,2,3,5}
  6. Pobierz element ze zbioru INPUT. Element to ‘4’. Porównujesz ten element kolejno z elementami zbioru OUTPUT:
    1. porównujesz ‘1’ z ‘4’. ‘4’ jest większe niż ‘1’, więc nic nie zmieniasz,
    2. porównujesz ‘2’ z ‘4’. ‘4’ jest większe niż ‘2’, więc nic nie zmieniasz,
    3. porównujesz ‘3’ z ‘4’. ‘4’ jest większe niż ‘3’, więc nic nie zmieniasz,
    4. porównujesz ‘5’ z ‘4’. ‘5’ jest większe niż ‘4’, więc wstawiasz ‘4’ na aktualnym indeksie tablic tj. [3].

    Zbiory wyglądają następująco:

    INPUT = {}
    OUTPUT = {1,2,3,4,5}

Posortowałeś tablicę w 6 prostych krokach, z czego kroki 2-6 to tak na prawdę taki sam algorytm.

Implementacja algorytmu sortowania przez wstawienie w C#

Od razu zaprezentuję implementację algorytmu w języku C#. Przedstawiam 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 SimpleInsertionSort
{
    public void Sort(int[] table)
    {
        List<int> output = new List<int>();
        foreach (int elementToSort in table)
        {
            int indexInSorted = 0;
            while (indexInSorted < output.Count && output[indexInSorted] <= elementToSort)
            {
                indexInSorted++;
            }
            output.Insert(indexInSorted, elementToSort);
        }
        for (int index = 0; index < table.Length; ++index)
        {
            table[index] = output[index];
        }
    }
}
Algorytm składa się z kilku pętli. Na samym wejściu tworzony jest zbiór danych wyjściowych (wykorzystałem tutaj List<T> aby uprościć implementację). Następnie zaczyna się główna pętla algorytmu, która enumeruje się po wszystkich elementach tablicy wejściowej. Później algorytm dochodzi do wewnętrzenej pętli, która wylicza miejsce w tablicy output, gdzie wstawić dany element. Do wyliczenia wykorzystywany jest warunek, który jest spełniony do czasu, kiedy obliczony indeks wskazuje na miejsce za ostatnim elementem tablicy, albo element spod obliczonego indeksu jest mniejszy/równy niż sprawdzany. Po wyliczeniu indeksu, wykorzystując funkcję List<int>.Insert(int, int) wstawiam element na wskazanym miejscu. Nie muszę się martwić o przesuwanie pozostałych elementów, implementacja funkcji zrobi to za mnie. Pętla główna kończy się po przeanalizowaniu wszystkich elementów. Ostatnia pętla po prostu przepisuje obliczone wyniki do tablicy wejściowej.

Implementacja za pomocą interfejsu IComparable

W bardziej uogólnionej implementacji algorytmu – takiej dającej się zastosować dla większej ilości rodzajów obiektów tj. nie ograniczających się do int – należy użyć IComparable. Implementacja tej wersji algorytmu prezentuje się następująco:

public class InsertionSort : ISortAlgorithm
{
    public void Sort(IComparable[] table)
    {
        List<IComparable> output = new List<IComparable>();
        foreach (IComparable elementToSort in table)
        {
            int indexInSorted = 0;
            while (indexInSorted < output.Count && output[indexInSorted].CompareTo(elementToSort) <= 0)
            {
                indexInSorted++;
            }
            output.Insert(indexInSorted, elementToSort);
        }
        for (int index = 0; index < table.Length; ++index)
        {
            table[index] = output[index];
        }
    }
}

Jak widać są dwie proste zmiany:

  1. zmiana typów int -> IComparable,
  2. zmiana warunku na taki wykorzystujący funkcję CompareTo. Podyktowane jest to tym, że typów IComparable nie można porównywać bezpośrednio za pomocą operatora <=, zamiast tego trzeba użyć wspomnianej funkcji. Jeżeli wynik funkcji jest <= 0, to znaczy, że obiekt główny (ten na którym wołamy funkcję) jest mniejszy/równy do porównywalnego. Czyli dokładnie o taki warunek chodzi.

Modyfikacja algorytmu przez wstawienie

Istnieje opcja modyfikacja algorytmu, tak aby zmniejszyć liczbę dokonywanych porównań. Zamiast enumerować się po każdym elemencie tablicy już posortowanej – kojarzysz tą wewnętrzną pętlę while? No właśnie –  można użyć wyszukiwania, które dobrze działa na posortowanych tablicach (bo ta tablica jest przecież posortowana). Przykładem takiego algorytmu może być przeszukiwanie binarne. Zamiast jednak pisać od zera ten algorytm, w tym przykładzie skorzystamy z gotowej implementacji MS tj. funkcji List<T>.BinarySearch. Implementacja zmodyfikowanego algorytmu wygląda następująco:

public class InsertionSortOptymalized : ISortAlgorithm
{
    public void Sort(IComparable[] table)
    {
        List<IComparable> output = new List<IComparable>();
        foreach (IComparable elementToSort in table)
        {
            int indexInSorted = output.BinarySearch(elementToSort);
            if (indexInSorted < 0)
            {
                indexInSorted = Math.Abs(indexInSorted) - 1;
            }
            output.Insert(indexInSorted, elementToSort);
        }
        for (int index = 0; index < table.Length; ++index)
        {
            table[index] = output[index];
        }
    }
}

W powyższym kodzie zastąpiono wewnętrzną pętlę while funkcją wyszukiwana binarnego. Implementacja BinarySearch zwraca indeks znalezionego elementu, albo informacje gdzie dany element by się znalazł, jeżeli taki nie istnieje w przeszukiwanej kolekcji. Jednak dane te mają “dziwny” format. Otóż, jeżeli element nie zostanie znaleziony, to zwracany jest indeks pod jakim by się znalazł, ale indeks ten jest zanegowany i liczony od 1 (nie od 0 jak to normalni ludzie robią ;)). Czyli np. indeks o wartości -1, oznacza, że byłby to pierwszy element listy. Dlatego też jeżeli wartość obliczonego indeksu jest mniejsza od 0, obliczam jego skorygowaną wartość za pomocą Math.Abs(indexInSorted) -1, czyli zmieniam go na wartość dodatnią i pomniejszam o 1,  tak aby liczył od 0 nie od 1. To cała filozofia. Zabieg taki pozwolił ograniczyć złożoność wyszukiwana z O(n^2) do O(n*logn). Nie zmienia to jednak złożoności obliczeniowej całego algorytmu, ponieważ nadal trzeba przesunąć O(n^2) elementów.

Testowanie algorytmu

Aby przetestować wszystkie 3 wersje algorytmu, posłużę się już wcześniej przygotowanymi danymi (dane te były przygotowane w ramach artykułu o Bubble Sort). Kod testujący wygląda następująco:

[TestClass]
public class TestInsertionSort
{
    [TestMethod]
    public void SimpleInsertionSort()
    {
        SimpleInsertionSort sort = new SimpleInsertionSort();
        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 InsertionSort()
    {
        InsertionSort sort = new InsertionSort();
        ComparableInt[] test1 = SortData.Example1Input;
        sort.Sort(test1);
        Assert.IsTrue(Helpers.Equals(SortData.Example1Output, test1));
    }
 
    [TestMethod]
    public void InsertionSortOptimized()
    {
        InsertionSortOptimized sort = new InsertionSortOptimized();
        ComparableInt[] test1 = SortData.Example1Input;
        sort.Sort(test1);
        Assert.IsTrue(Helpers.Equals(SortData.Example1Output, test1));
    }
}

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

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.