Sortowanie Przez Wstawianie

Sortowanie przez wstawianie to prosty algorytm sortowania,
który działa podobnie do sposobu sortowania kart do gry.

Powiedzmy że mamy tablicę która jest wirtualnie podzielona
na posortowaną i nieposortowaną część.
Wartości z nieposortowanej części są pobierane i umieszczane
we właściwej pozycji w posortowanej części.

Algorytm wygląda tak:

Aby posortować tablicę o rozmiarze n w kolejności rosnącej wykonujemy
następujące kroki:

krok 1

Iterujemy po tablicy zaczynając od elementu drugiego aż do ostatniego elementu tablicy.

krok 2

Porównujemy bieżący element z jego poprzednikiem.

krok 3

Jeśli bieżący element jest mniejszy niż jego poprzednik,
porównujemy go z wcześniejszymi elementami jeśli takie są.
Następnie przesuwamy większe elementy o jedną pozycję w górę,
aby zrobić miejsce na zamieniony element.

Zobaczmy to na przykładzie:

Mamy tablicę 5 elementową [42, 41, 43, 25, 26 ]
którą chcemy posortować w kolejności rosnącej.

krok 1 – Iterujemy po tablicy zaczynając od elementu drugiego aż do ostatniego elementu tablicy. Jak zapewne wiemy Drugi element tablicy ma indeks 1.
krok 2 – Porównujemy bieżący element z jego poprzednikiem.
krok 3 – Jeśli bieżący element jest mniejszy niż jego poprzednik,
porównujemy go z wcześniejszymi elementami jeśli takie są.
Następnie przesuwamy większe elementy o jedną pozycję w górę,
aby zrobić miejsce na zamieniony element.

Ponieważ 41 jest mniejsze niż 42, przesuwamy 42 i wstawiamy 41 przed 42
41, 42, 43, 25, 26

Wykonujemy kolejną iterację pętli
43 pozostanie na swoim miejscu, ponieważ wszystkie elementy go poprzedzające są mniejsze niż 43
41, 42, 43, 25, 26

Wykonujemy kolejną iterację pętli
25 przesunie się na początek, a wszystkie inne elementy od 41 do 43 przesuną się o jedną pozycję do przodu w stosunku do ich aktualnej pozycji.
25, 41, 42, 43, 26

Wykonujemy kolejną iterację pętli
26 przesunie się na pozycję po 25, a elementy od 41 do 43 przesuną się o jedną pozycję do przodu w stosunku do ich aktualnej pozycji.
25, 26, 41, 42, 43

Otrzymujemy posortowaną tablicę w kolejności rosnącej.

Implementacja w kodzie C#

public class InsertionSort
{
        public static void Main(string[] args)
        {
            int[] arrayToSort = { 42, 41, 43, 25, 26 };
            SortArray(arrayToSort);
            PrintArray(arrayToSort);
        }

        private static void SortArray(int[] data) 
        {
            for (int i = 1; i < data.Length; ++i)
            {
                int current = data[i];
                int j = i - 1;
  
                while (j >= 0 && data[j] > current)
                {
                    data[j + 1] = data[j];
                    j = j - 1;
                }

                data[j + 1] = current;
            }
        }

        private static void PrintArray(int[] data)
        {
	    Console.Write("Posortowana tablica:\n");

            for (int i = 0; i < data.Length; ++i)
                Console.Write(data[i] + " ");

            Console.Write("\n");
        }
}

Wyjście:

25 26 41 42 43

Sortowanie przez wstawianie zajmuje maksymalny czas,
jeśli elementy są sortowane w odwrotnej kolejności.
I zajmuje minimum czasu, gdy elementy są już posortowane.

Kiedy możemy zastosować

Sortowanie przez wstawianie jest używane, gdy liczba elementów jest niewielka.
Może to być również przydatne, gdy tablica wejściowa jest prawie posortowana,
tylko kilka elementów jest niewłaściwie umieszczonych w pełnej dużej tablicy.