Sortowanie Przez Wstawianie

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.

12 comments

  1. Twoje podejście do rozwiązania problemu jest bardzo kreatywne. Nigdy bym nie pomyślał/a o tym w taki sposób

  2. Podoba mi się, jak przedstawiasz skomplikowane tematy w sposób zrozumiały dla wszystkich. To naprawdę cenne, zwłaszcza dla osób, które dopiero zaczynają swoją przygodę z programowaniem

  3. Ciekawe spojrzenie na temat [temat]. Naprawdę rozbudziłeś moją ciekawość

  4. Choć sortowanie przez wstawianie jest prostym algorytmem, może być mniej efektywne niż bardziej zaawansowane techniki sortowania, zwłaszcza dla dużych zestawów danych. Zastanów się, czy jest to najlepszy wybór w zależności od rozmiaru problemu.

  5. Podoba mi się, jak klarownie tłumaczysz skomplikowane koncepcje. To naprawdę pomaga zrozumieć temat.”

  6. Masz dar do tworzenia artykułów, które są jednocześnie dla początkujących i zaawansowanych. To trudne do osiągnięcia

  7. Twój artykuł jest świetnym punktem wyjścia dla osób, które chcą zgłębić się w temat

  8. To jest dokładnie to, czego szukałem. Bardzo praktyczne i konkretne porady

  9. Masz zdolność tłumaczenia skomplikowanych koncepcji na prosty język. Świetne

  10. peml_viniry-na-zuby.ru_ pisze:

    Bardzo podoba mi się, jak uwzględniasz praktyczne aspekty tematu sortowania. To sprawia, że artykuł jest bardziej przydatny w codziennej pracy

  11. Świetny artykuł! Naprawdę dobrze wyjaśniasz trudne koncepcje w sposób zrozumiały

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *