Sortowanie przez wstawianie

6.1 Definicja sortowania przez wstawianie

Sortowanie przez wstawianie (Insertion Sort) — to algorytm sortowania, który buduje posortowaną tablicę (lub listę) po jednym elemencie naraz. Pobiera każdy element z części nieposortowanej i wstawia go na właściwe miejsce w części posortowanej.

Zasada działania:

1. Zaczynamy od drugiego elementu tablicy (pierwszy element jest uznawany za posortowany).
2. Porównujemy bieżący element z poprzednimi i przesuwamy go w lewo, dopóki nie znajdziemy właściwego miejsca.
3. Powtarzamy proces dla wszystkich elementów tablicy, wstawiając każdy nowy element na właściwe miejsce w już posortowanej części tablicy.

Złożoność czasowa i przestrzenna sortowania przez wstawianie

Złożoność czasowa:

• W najgorszym przypadku: O(n^2) — występuje, gdy elementy są początkowo uporządkowane w odwrotnej kolejności.
• W przeciętnym przypadku: O(n^2) — występuje dla losowego rozmieszczenia elementów.
• W najlepszym przypadku: O(n) — występuje, gdy elementy są już posortowane.

Złożoność przestrzenna:

O(1) — ponieważ algorytm używa stałej ilości dodatkowej pamięci (tylko kilka zmiennych do przechowywania wartości tymczasowych).

6.2 Analiza działania algorytmu

Na kolejnym etapie algorytmu mamy taką sytuację:

• Mamy bieżący element z indeksem i.
• Wszystkie elementy po lewej stronie są już posortowane od najmniejszego do największego.
• Staramy się wstawić nasz bieżący element do posortowanej części tablicy, aby nie naruszyć porządku sortowania.

Próba wstawienia elementu do posortowanej części tablicy wygląda tak:

1. Zmienna j w pętli przyjmuje wartość od i - 1 do 0.
2. Jeśli bieżący (i-ty) element jest mniejszy od j-tego, przesuwamy wartość j-tego elementu o 1 w prawo.

Przykład: bieżąca sytuacja:

• Na zielono zaznaczone są już posortowane elementy.
• Na różowo — elementy, które jeszcze nie zostały posortowane.
• Bieżący element pod indeksem 5 — zaznaczony brązowym.

Próbujemy znaleźć właściwe miejsce naszemu bieżącemu elementowi w posortowanej części tablicy.

Krok 1 — zapisujemy wartość bieżącego elementu w zmiennej key.

Krok 2 — element No4 jest większy od key? (10 jest większe od 5?) Zatem przesuwamy element No4 w prawo:

Krok 3 — element No3 jest większy od key? (8 jest większe od 5?) Zatem przesuwamy element No3 w prawo:

Krok 4 — element No2 jest większy od key? (6 jest większe od 5?) Zatem przesuwamy element No2 w prawo:

Krok 5 — element No1 jest większy od key? (4 jest większe od 5?) Nie. Zatem zapisujemy element key tam, gdzie był element No2.

Po wstawieniu elementu No5 na właściwe miejsce, przechodzimy do elementu No6 i próbujemy znaleźć mu miejsce w posortowanej części tablicy:

Następnie bierzemy siódmy element:

Następnie ósmy:

6.3 Implementacja algorytmu sortowania przez wstawianie

Tak wygląda ten algorytm w Python:

def insertion_sort(arr):
    # Przechodzimy przez wszystkie elementy tablicy, zaczynając od drugiego
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1 # Przesuwamy elementy arr[0..i - 1], które są większe od klucza, o jedno miejsce do przodu while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1
        arr[j + 1] = key # Wstawiamy klucz na właściwe miejsce
    return arr  # Zwracamy posortowaną tablicę
        
# Przykład użycia:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Posortowana tablica:", sorted_arr)
# Wynik: Posortowana tablica: [5, 6, 11, 12, 13]

Wyjaśnienie:

• Zapisujemy bieżący element w key
• Przesuwamy wszystkie elementy posortowanej części tablicy w prawo
• Wstawiamy nasz element na odpowiednie miejsce

Przykład działania algorytmu

Weźmy przykład tablicy: [12, 11, 13, 5, 6]

1. Pierwsze przejście (i = 1):

• Porównujemy 11 i 12, przesuwamy 12 w prawo.
• Tablica: [11, 12, 13, 5, 6]

2. Drugie przejście (i = 2):

• 13 jest już na swoim miejscu.
• Tablica: [11, 12, 13, 5, 6]

3. Trzecie przejście (i = 3):

• Porównujemy 5 z 13, 12 i 11, przesuwamy wszystko w prawo.
• Tablica: [5, 11, 12, 13, 6]

4. Czwarte przejście (i = 4):

• Porównujemy 6 z 13, 12 i 11, przesuwamy wszystko w prawo.
• Tablica: [5, 6, 11, 12, 13]

Algorytm kończy się, gdy wszystkie elementy są posortowane.