Zasada dzialania insertion sort, wizualizacja krok po kroku, implementacja w Pythonie, zlozonosc obliczeniowa O(n²)
ð Podstawa programowa: I.2cSortowanie przez wstawianie (ang. insertion sort) to jeden z najprostszych i najbardziej intuicyjnych algorytmow sortowania. Jego dzialanie mozna porownac do sposobu, w jaki ukladamy karty w rece podczas gry - bierzemy kolejna karte i wstawiamy ja na odpowiednie miejsce wsrod juz posortowanych kart.
Algorytm dzieli tablice na dwie czesci: posortowana (na poczatku zawiera tylko pierwszy element) i nieposortowana (reszta elementow). W kazdym kroku bierzemy pierwszy element z czesci nieposortowanej i wstawiamy go na wlasciwe miejsce w czesci posortowanej.
Posortujmy tablice [5, 3, 8, 1, 6] algorytmem insertion sort:
Tablica poczatkowa: [5, 3, 8, 1, 6]
Krok 1: klucz = 3
[5, 3, 8, 1, 6] -> 3 < 5, przesun 5 w prawo
[_, 5, 8, 1, 6] -> wstaw 3 na pozycje 0
[3, 5, 8, 1, 6] posortowane: [3, 5]
Krok 2: klucz = 8
[3, 5, 8, 1, 6] -> 8 > 5, nie przesuwaj
[3, 5, 8, 1, 6] posortowane: [3, 5, 8]
Krok 3: klucz = 1
[3, 5, 8, 1, 6] -> 1 < 8, przesun 8 w prawo
[3, 5, _, 8, 6] -> 1 < 5, przesun 5 w prawo
[3, _, 5, 8, 6] -> 1 < 3, przesun 3 w prawo
[_, 3, 5, 8, 6] -> wstaw 1 na pozycje 0
[1, 3, 5, 8, 6] posortowane: [1, 3, 5, 8]
Krok 4: klucz = 6
[1, 3, 5, 8, 6] -> 6 < 8, przesun 8 w prawo
[1, 3, 5, _, 8] -> 6 > 5, nie przesuwaj
[1, 3, 5, 6, 8] -> wstaw 6 na pozycje 3
[1, 3, 5, 6, 8] posortowane: [1, 3, 5, 6, 8]
Wynik: [1, 3, 5, 6, 8]def insertion_sort(tablica):
"""Sortowanie przez wstawianie - rosnaco."""
n = len(tablica)
for i in range(1, n):
klucz = tablica[i] # element do wstawienia
j = i - 1 # indeks ostatniego posortowanego
# Przesuwaj elementy wieksze od klucza w prawo
while j >= 0 and tablica[j] > klucz:
tablica[j + 1] = tablica[j]
j -= 1
# Wstaw klucz na wlasciwe miejsce
tablica[j + 1] = klucz
return tablica
# Przyklad uzycia
dane = [5, 3, 8, 1, 6]
print(f"Przed: {dane}")
insertion_sort(dane)
print(f"Po: {dane}")
# Przed: [5, 3, 8, 1, 6]
# Po: [1, 3, 5, 6, 8]def insertion_sort_verbose(tablica):
"""Wersja z wypisywaniem stanu tablicy po kazdym kroku."""
n = len(tablica)
print(f"Start: {tablica}")
for i in range(1, n):
klucz = tablica[i]
j = i - 1
while j >= 0 and tablica[j] > klucz:
tablica[j + 1] = tablica[j]
j -= 1
tablica[j + 1] = klucz
print(f"Krok {i}: klucz={klucz} -> {tablica}")
return tablica
# Test
insertion_sort_verbose([5, 3, 8, 1, 6])Analiza zlozonosci algorytmu sortowania przez wstawianie:
Posortuj recznie (na kartce) tablice [7, 2, 4, 9, 1, 3] algorytmem sortowania przez wstawianie. Zapisz stan tablicy po kazdym kroku. Nastepnie zweryfikuj wynik w programie.
# Reczne sortowanie [7, 2, 4, 9, 1, 3]:
# Krok 1: klucz=2, 2<7 -> [2, 7, 4, 9, 1, 3]
# Krok 2: klucz=4, 4<7 -> [2, 4, 7, 9, 1, 3]
# Krok 3: klucz=9, 9>7 -> [2, 4, 7, 9, 1, 3]
# Krok 4: klucz=1, 1<9<7<4<2 -> [1, 2, 4, 7, 9, 3]
# Krok 5: klucz=3, 3<9<7<4, 3>2 -> [1, 2, 3, 4, 7, 9]
# Weryfikacja w Pythonie:
def insertion_sort_verbose(tab):
for i in range(1, len(tab)):
klucz = tab[i]
j = i - 1
while j >= 0 and tab[j] > klucz:
tab[j + 1] = tab[j]
j -= 1
tab[j + 1] = klucz
print(f"Krok {i}: klucz={klucz} -> {tab}")
insertion_sort_verbose([7, 2, 4, 9, 1, 3])Napisz funkcje insertion sort, ktora zlicza liczbe porownan i przesuniec elementow. Program powinien posortowac tablice i wyswietlic statystyki.
def insertion_sort_stats(tablica):
"""Insertion sort z licznikami operacji."""
porownania = 0
przesuniecia = 0
n = len(tablica)
for i in range(1, n):
klucz = tablica[i]
j = i - 1
while j >= 0:
porownania += 1
if tablica[j] > klucz:
tablica[j + 1] = tablica[j]
przesuniecia += 1
j -= 1
else:
break
tablica[j + 1] = klucz
return tablica, porownania, przesuniecia
# Test na roznych tablicach
testy = [
[5, 3, 8, 1, 6],
[1, 2, 3, 4, 5], # juz posortowana
[5, 4, 3, 2, 1], # odwrotnie
]
for tab in testy:
kopia = tab[:]
wynik, por, prz = insertion_sort_stats(kopia)
print(f"{tab} -> {wynik}")
print(f" Porownania: {por}, Przesuniecia: {prz}")Zaimplementuj zarowno insertion sort jak i bubble sort. Posortuj ta sama losowa tablice 100 elementow obydwoma metodami i porownaj liczbe operacji. Ktory algorytm wykonal mniej porownan?
import random
def insertion_sort_count(tab):
porownania = 0
for i in range(1, len(tab)):
klucz = tab[i]
j = i - 1
while j >= 0 and tab[j] > klucz:
porownania += 1
tab[j + 1] = tab[j]
j -= 1
if j >= 0:
porownania += 1
tab[j + 1] = klucz
return porownania
def bubble_sort_count(tab):
porownania = 0
n = len(tab)
for i in range(n - 1):
for j in range(n - 1 - i):
porownania += 1
if tab[j] > tab[j + 1]:
tab[j], tab[j + 1] = tab[j + 1], tab[j]
return porownania
# Generuj losowa tablice
oryginalna = [random.randint(1, 1000) for _ in range(100)]
kopia1 = oryginalna[:]
kopia2 = oryginalna[:]
por_ins = insertion_sort_count(kopia1)
por_bub = bubble_sort_count(kopia2)
print(f"Insertion sort: {por_ins} porownan")
print(f"Bubble sort: {por_bub} porownan")
print(f"Insertion sort wykonal {por_bub - por_ins} porownan mniej")Zoptymalizuj insertion sort uzywajac wyszukiwania binarnego do znalezienia pozycji wstawienia elementu (binary insertion sort). Zmniejszy to liczbe porownan, chocia liczba przesuniec pozostanie taka sama.
def binary_insertion_sort(tablica):
"""Insertion sort z wyszukiwaniem binarnym."""
for i in range(1, len(tablica)):
klucz = tablica[i]
# Wyszukiwanie binarne pozycji wstawienia
lewy = 0
prawy = i
while lewy < prawy:
srodek = (lewy + prawy) // 2
if tablica[srodek] > klucz:
prawy = srodek
else:
lewy = srodek + 1
# Przesun elementy w prawo
for j in range(i, lewy, -1):
tablica[j] = tablica[j - 1]
# Wstaw klucz
tablica[lewy] = klucz
return tablica
# Test
dane = [12, 5, 3, 8, 1, 9, 2, 7]
print(f"Przed: {dane}")
binary_insertion_sort(dane)
print(f"Po: {dane}")
# Przed: [12, 5, 3, 8, 1, 9, 2, 7]
# Po: [1, 2, 3, 5, 7, 8, 9, 12]