Sortowanie przez wstawianie

Sortowanie przez wstawianie (ang. insertion sort) to prosty algorytm sortowania, który działa w taki sam sposób, w jaki sortujemy karty do gry, które trzymamy w rękach. Jest on wydajny dla zbiorów o niewielkiej liczebności.

Złożoność czasowa sortowania przez wstawianie:

• Najlepszy przypadek: O(n), jeśli lista jest już posortowana, gdzie n jest liczbą elementów na liście
• Przypadek przeciętny: O(n²), jeśli lista jest uporządkowana losowo
• Najgorszy przypadek: O(n²), jeśli lista jest w odwrotnej kolejności

Sortowanie przez wstawianie ma złożoność pamięciowa O(1), co czyni go algorytmem sortowania efektywnym pod względem wykorzystania pamięci.

Implementacja sortowania przez wstawianie w Pythonie:

# definicja funkcji sortowania przez wstawianie rosnąco
def insertionSort(arr):
    n = len(arr)
      
    if n <= 1:
        return  # jeśli tablica ma jeden element lub jest pusta, to znaczy że jest już posortowana i należy zakończyć funkcję
 
    for i in range(1, n): # iteruj po tablicy zaczynając od drugiego elementu
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]  # przesuń elementy mniejsze w prawo
            j -= 1
        arr[j+1] = key  # umieść sprawdzany element w prawidłowym miejscu

# przykładowe dane wejściowe do posortowania
arr = [12, 11, 13, 5, 6]

# wywołanie funkcji sortowania
insertionSort(arr)

# wyświetlenie posortowanej tablicy
print(arr)