Sortowanie przez Wstawianie w C#

Czym jest sortowanie przez wstawianie?

Sortowanie przez wstawianie (ang. insertion sort) to jeden z najprostszych algorytmów sortowania, który naturalnie odzwierciedla sposób, w jaki układamy karty do gry w ręce. Bierzesz kolejną kartę i wkładasz ją na właściwe miejsce wśród już ułożonych – dokładnie tak samo działa ten algorytm.

Tablica jest wirtualnie podzielona na dwie części: posortowaną (początkowo zawiera jeden element) i nieposortowaną (cała reszta). W każdej iteracji pobieramy pierwszy element z części nieposortowanej i wstawiamy go we właściwe miejsce w części posortowanej.

Kluczowa intuicja:
Nie zamieniamy elementów miejscami jak w bubble sort – przesuwamy elementy, żeby zrobić miejsce dla wstawianego klucza.
To subtelna, ale ważna różnica wpływająca na liczbę operacji.

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.

Jak działa algorytm – krok po kroku

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

Iteracja 1 (i=1): Klucz = 41. Porównujemy z 42 → 42 > 41, przesuwamy 42 w prawo. Wstawiamy 41 na pozycję 0. Wynik: [41, 42, 43, 25, 26]

Iteracja 2 (i=2): Klucz = 43. Poprzednik 42 < 43 → nic nie robimy. Wynik: [41, 42, 43, 25, 26]

Iteracja 3 (i=3): Klucz = 25. Przesuwamy kolejno 43, 42, 41. Wstawiamy 25 na pozycję 0. Wynik: [25, 41, 42, 43, 26]

Iteracja 4 (i=4): Klucz = 26. Przesuwamy 43, 42, 41. Wstawiamy 26 na pozycję 1. Wynik: [25, 26, 41, 42, 43] ✓

Skorzystaj z interaktywnej wizualizacji poniżej – użyj przycisku Następny krok, żeby przejść przez każdą operację osobno i zobaczyć dokładnie co się dzieje.

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);
        }

        /// <summary>
        /// Sortuje tablicę w miejscu (in-place) w kolejności rosnącej.
        /// Złożoność: O(n²) worst/average, O(n) best (tablica już posortowana).
        /// </summary>
        private static void SortArray(int[] data) 
        {
            for (int i = 1; i < data.Length; i++)
            {
                int current = data[i];    // Element do wstawienia
                int j = i - 1;
  
                // Przesuwamy elementy większe od current o jedną pozycję w prawo
                while (j >= 0 && data[j] > current)
                {
                    data[j + 1] = data[j];
                    j--;
                }

                // Wstawiamy key na właściwe miejsce
                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.

Analiza złożoności

Przypadek	Złożoność czasowa	Kiedy występuje
Best case	O(n)	Tablica już posortowana – pętla while nigdy nie wchodzi w ciało
Average case	O(n²)	Losowa kolejność elementów
Worst case	O(n²)	Tablica posortowana odwrotnie – maksymalna liczba przesunięć

Złożoność przestrzenna: O(1) – sortowanie odbywa się in-place, bez dodatkowej pamięci.

Stabilność: Insertion sort jest algorytmem stabilnym – elementy o równych kluczach zachowują oryginalną kolejność.
To ważne np. przy sortowaniu obiektów według jednej właściwości, gdy inne właściwości są już posortowane.

---

Kiedy używać insertion sort w praktyce?

Tak – dobre przypadki użycia:

Małe tablice (n < 20–50).
Algorytmy O(n log n) jak Quicksort czy Mergesort mają narzut stały (rekurencja, podział, scalanie).
Dla małych n insertion sort po prostu wygrywa z powodu niskiego kosztu stałego.
Dlatego hybrydowe implementacje jak Timsort (Python, Java) i Introsort (.NET) przełączają się na insertion sort poniżej pewnego progu rozmiaru.

Tablica prawie posortowana.
Jeśli każdy element jest co najwyżej k pozycji od właściwego miejsca, złożoność spada do O(n·k).
W praktyce: dane strumieniowe z drobnymi zakłóceniami, logi z nieznacznym rozjazdem timestampów, dane z czujników.

Sortowanie online (online sorting).
Insertion sort naturalnie obsługuje dane napływające po jednym elemencie – każdy nowy element po prostu wstawiamy na właściwe miejsce bez ponownego sortowania całości.

Nie – czego unikać:

Dla dużych, losowo ułożonych zbiorów danych (n > kilkaset) zawsze sięgaj po Array.Sort() z .NET, który używa Introsort – hybrydy Quicksort + Heapsort + Insertion sort z gwarancją O(n log n) worst-case.

---

Ciekawostka: Insertion sort w .NET Runtime

Array.Sort<T>() w .NET korzysta z Introsort. Gdy rozmiar podtablicy w rekurencji spadnie poniżej 16 elementów, algorytm przełącza się właśnie na insertion sort.
Możesz to zobaczyć w źródłach CoreCLR w pliku ArraySortHelper.cs. To oznacza, że za każdym razem gdy wywołujesz Array.Sort() na małej tablicy – insertion sort już pracuje w tle.

---

Podsumowanie

Sortowanie przez wstawianie to algorytm, który każdy programista powinien rozumieć w detalach – nie dlatego, że będziesz go pisać od zera w produkcji, ale dlatego że:

• ilustruje fundament: jak analiza złożoności przekłada się na realne zachowanie kodu,
• jest cegiełką w hybrydowych algorytmach używanych przez wszystkie nowoczesne środowiska,
• uczy myślenia o in-place, stabilności i adaptacyjności – pojęciach kluczowych przy wyborze algorytmu.

Złożoność O(n²) nie dyskwalifikuje algorytmu – dyskwalifikuje go użycie w złym kontekście.

Zobacz także — powiązane artykuły

👉 Tworzenie klas i obiektów w C# — kompletny przewodnik

👉LINQ w C# — przetwarzanie kolekcji bez pętli – zobacz w kursie LINQ w C# -czytelny kod, wydajne zapytania

👉 Typy wartościowe vs referencyjne w C# — jak działa pamięć – zobacz w kursie C# Podstawy Programowania: Twój Pierwszy Krok w Świat Kodowania

Dołącz do Listy VIP

I otrzymaj roadmapę Junior .NET Developer oraz najlepszą ofertę, gdy tylko ruszą zapisy!!!

Dołącz –>

Kontakt: mariuszjurczenko@dev-hobby.pl

Zero spamu. Możesz wypisać się w każdej chwili.