Sortowanie babelkowe i przez wstawianie - implementacja, porownanie, pomiar czasu
ð Podstawa programowa: II.1+I.2cSortowanie to jeden z najczesciej wykonywanych procesow w informatyce. Posortowane dane pozwalaja na szybsze wyszukiwanie (np. wyszukiwanie binarne), lepsze wyswietlanie informacji i efektywniejsze przetwarzanie. Zrozumienie algorytmow sortowania to fundament myslenia algorytmicznego.
Zasada dzialania: Porownujemy pary sasiadujacych elementow i zamieniamy je miejscami, jesli sa w zlej kolejnosci. Powtarzamy przejscie przez liste, dopoki nie bedzie posortowana. Nazwe zawdziecza temu, ze wieksze elementy "wyplywaja" na koniec listy jak babelki.
def sortowanie_babelkowe(lista):
n = len(lista)
for i in range(n - 1):
zamiana = False
for j in range(n - 1 - i):
if lista[j] > lista[j + 1]:
lista[j], lista[j + 1] = lista[j + 1], lista[j]
zamiana = True
if not zamiana: # optymalizacja - lista juz posortowana
break
return lista
# Przyklad
dane = [64, 34, 25, 12, 22, 11, 90]
print(f"Przed: {dane}")
sortowanie_babelkowe(dane)
print(f"Po: {dane}")Analiza:
Zasada dzialania: Dzialamy jak przy ukladaniu kart - bierzemy kolejny element i wstawiamy go na odpowiednie miejsce wsrod juz posortowanych elementow. Czesc posortowana rosnie z kazdym krokiem.
def sortowanie_przez_wstawianie(lista):
n = len(lista)
for i in range(1, n):
klucz = lista[i]
j = i - 1
while j >= 0 and lista[j] > klucz:
lista[j + 1] = lista[j]
j -= 1
lista[j + 1] = klucz
return lista
# Przyklad
dane = [64, 34, 25, 12, 22, 11, 90]
print(f"Przed: {dane}")
sortowanie_przez_wstawianie(dane)
print(f"Po: {dane}")Analiza:
Mozemy empirycznie porownac oba algorytmy, mierzac czas ich dzialania dla roznych rozmiarow danych:
import time
import random
def pomiar_czasu(funkcja_sort, dane):
kopia = dane.copy()
start = time.time()
funkcja_sort(kopia)
koniec = time.time()
return koniec - start
# Generowanie danych testowych
for rozmiar in [100, 500, 1000, 2000, 5000]:
dane = [random.randint(1, 10000) for _ in range(rozmiar)]
t_babelkowe = pomiar_czasu(sortowanie_babelkowe, dane)
t_wstawianie = pomiar_czasu(sortowanie_przez_wstawianie, dane)
t_wbudowane = pomiar_czasu(sorted, dane)
print(f"n={rozmiar:5d} | Babelkowe: {t_babelkowe:.4f}s | "
f"Wstawianie: {t_wstawianie:.4f}s | "
f"sorted(): {t_wbudowane:.6f}s")sorted() w Pythonie uzywa algorytmu Timsort (O(n log n)), ktory jest wielokrotnie szybszy od sortowan O(n^2) dla duzych danych. Jednak znajomosc prostych algorytmow jest kluczowa dla zrozumienia zlozonosci obliczeniowej.
Zaimplementuj sortowanie babelkowe, ktore po kazdym przejsciu (iteracji zewnetrznej petli) wypisuje aktualny stan listy. Przetestuj na liscie [5, 3, 8, 1, 9, 2].
def babelkowe_wizualizacja(lista):
n = len(lista)
print(f"Start: {lista}")
for i in range(n - 1):
for j in range(n - 1 - i):
if lista[j] > lista[j + 1]:
lista[j], lista[j + 1] = lista[j + 1], lista[j]
print(f"Przejscie {i+1}: {lista}")
return lista
babelkowe_wizualizacja([5, 3, 8, 1, 9, 2])Zmodyfikuj oba algorytmy sortowania tak, aby zliczaly liczbe porownan i zamian. Porownaj wyniki dla listy losowej, posortowanej rosnaco i posortowanej malejaco (po 20 elementow).
def babelkowe_statystyki(lista):
n = len(lista)
porownania = 0
zamiany = 0
for i in range(n - 1):
for j in range(n - 1 - i):
porownania += 1
if lista[j] > lista[j + 1]:
lista[j], lista[j + 1] = lista[j + 1], lista[j]
zamiany += 1
return porownania, zamiany
def wstawianie_statystyki(lista):
n = len(lista)
porownania = 0
przesuniecia = 0
for i in range(1, n):
klucz = lista[i]
j = i - 1
while j >= 0:
porownania += 1
if lista[j] > klucz:
lista[j + 1] = lista[j]
przesuniecia += 1
j -= 1
else:
break
lista[j + 1] = klucz
return porownania, przesuniecia
import random
losowa = [random.randint(1, 100) for _ in range(20)]
rosnaca = list(range(1, 21))
malejaca = list(range(20, 0, -1))
for nazwa, dane in [("Losowa", losowa), ("Rosnaca", rosnaca), ("Malejaca", malejaca)]:
p1, z1 = babelkowe_statystyki(dane.copy())
p2, z2 = wstawianie_statystyki(dane.copy())
print(f"{nazwa:8s} | Babelkowe: {p1} por., {z1} zam. | "
f"Wstawianie: {p2} por., {z2} przes.")Zmodyfikuj sortowanie przez wstawianie, aby sortowalo liste krotek (imie, ocena) wedlug oceny malejaco. Jesli oceny sa rowne, sortuj alfabetycznie po imieniu.
def sortuj_uczniow(lista):
n = len(lista)
for i in range(1, n):
klucz = lista[i]
j = i - 1
while j >= 0 and (lista[j][1] < klucz[1] or
(lista[j][1] == klucz[1] and lista[j][0] > klucz[0])):
lista[j + 1] = lista[j]
j -= 1
lista[j + 1] = klucz
return lista
uczniowie = [
("Anna", 5), ("Jan", 4), ("Kasia", 5),
("Piotr", 6), ("Marta", 4), ("Tomek", 6)
]
posortowani = sortuj_uczniow(uczniowie.copy())
for imie, ocena in posortowani:
print(f"{imie}: {ocena}")Napisz program, ktory mierzy czas sortowania babelkowego i przez wstawianie dla list o rozmiarach 100, 500, 1000, 2000, 3000. Wyniki zapisz do pliku CSV i (opcjonalnie) narysuj wykres za pomoca biblioteki matplotlib.
import time, random, csv
rozmiary = [100, 500, 1000, 2000, 3000]
wyniki = []
for n in rozmiary:
dane = [random.randint(1, 10000) for _ in range(n)]
kopia1 = dane.copy()
start = time.time()
sortowanie_babelkowe(kopia1)
t_bab = time.time() - start
kopia2 = dane.copy()
start = time.time()
sortowanie_przez_wstawianie(kopia2)
t_wst = time.time() - start
wyniki.append((n, t_bab, t_wst))
print(f"n={n}: babelkowe={t_bab:.4f}s, wstawianie={t_wst:.4f}s")
# Zapis do CSV
with open("porownanie_sortowania.csv", "w", newline="") as f:
writer = csv.writer(f)
writer.writerow(["rozmiar", "babelkowe", "wstawianie"])
writer.writerows(wyniki)
# Opcjonalnie - wykres
try:
import matplotlib.pyplot as plt
rozm = [w[0] for w in wyniki]
plt.plot(rozm, [w[1] for w in wyniki], 'r-o', label='Babelkowe')
plt.plot(rozm, [w[2] for w in wyniki], 'b-o', label='Wstawianie')
plt.xlabel('Rozmiar danych')
plt.ylabel('Czas [s]')
plt.title('Porownanie algorytmow sortowania')
plt.legend()
plt.grid(True)
plt.savefig('wykres_sortowania.png')
plt.show()
except ImportError:
print("Brak matplotlib - wykres nie zostal wygenerowany")