Implementacja i porownanie algorytmow sortowania w Pythonie
ð Podstawa programowa: II.1+I.2cSortowanie to jeden z najczesciej uzywanych algorytmow w informatyce. Posortowane dane pozwalaja na szybkie wyszukiwanie, latwiejsza analize i czytelna prezentacje. W klasie I poznalismy kilka algorytmow - teraz utrwalamy ich implementacje w Pythonie.
Porownujemy sasiednie elementy i zamieniamy je, jesli sa w zlej kolejnosci. Powtarzamy przejscia az lista bedzie posortowana:
def sortowanie_babelkowe(tab):
n = len(tab)
for i in range(n - 1):
zamiana = False
for j in range(n - 1 - i):
if tab[j] > tab[j + 1]:
tab[j], tab[j + 1] = tab[j + 1], tab[j]
zamiana = True
if not zamiana: # optymalizacja - wczesne zakonczenie
break
return tabZlozonosc: O(n^2) w najgorszym przypadku, O(n) w najlepszym (juz posortowana).
Budujemy posortowana czesc listy, wstawiajac kazdy kolejny element na wlasciwe miejsce:
def sortowanie_przez_wstawianie(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
return tabZlozonosc: O(n^2) w najgorszym przypadku, O(n) w najlepszym. Efektywne dla malych zbiorow danych.
W kazdym kroku znajdujemy minimum z nieposortowanej czesci i umieszczamy je na poczatku:
def sortowanie_przez_wybor(tab):
n = len(tab)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if tab[j] < tab[min_idx]:
min_idx = j
tab[i], tab[min_idx] = tab[min_idx], tab[i]
return tabZlozonosc: O(n^2) zawsze - niezaleznie od ukladu danych.
Zaimplementuj wszystkie trzy algorytmy sortowania z teorii. Przetestuj kazdy na tej samej liscie: [64, 34, 25, 12, 22, 11, 90]. Wyswietl liste po kazdym przejsciu, aby zobaczyc jak algorytm dziala krok po kroku.
def babelkowe_verbose(tab):
tab = tab.copy()
n = len(tab)
for i in range(n - 1):
for j in range(n - 1 - i):
if tab[j] > tab[j + 1]:
tab[j], tab[j + 1] = tab[j + 1], tab[j]
print(f" Przejscie {i+1}: {tab}")
return tab
dane = [64, 34, 25, 12, 22, 11, 90]
print("Sortowanie babelkowe:")
wynik = babelkowe_verbose(dane)
print(f" Wynik: {wynik}")Uzyj modulu time, aby zmierzyc czas dzialania kazdego algorytmu na losowej liscie 1000, 5000 i 10000 elementow. Porownaj wyniki z wbudowana funkcja sorted(). Przedstaw wyniki w tabeli.
import time
import random
def zmierz_czas(funkcja, dane):
kopia = dane.copy()
start = time.time()
funkcja(kopia)
return time.time() - start
for rozmiar in [1000, 5000, 10000]:
dane = [random.randint(1, 100000) for _ in range(rozmiar)]
print(f"\nRozmiar: {rozmiar}")
print(f" Babelkowe: {zmierz_czas(sortowanie_babelkowe, dane):.4f}s")
print(f" Przez wstawianie:{zmierz_czas(sortowanie_przez_wstawianie, dane):.4f}s")
print(f" Przez wybor: {zmierz_czas(sortowanie_przez_wybor, dane):.4f}s")
print(f" sorted(): {zmierz_czas(sorted, dane):.6f}s")Zmodyfikuj kazdy z trzech algorytmow sortowania tak, aby sortowal malejaco (od najwiekszego do najmniejszego). Dodaj parametr malejaco=False do kazdej funkcji, ktory zmienia kierunek sortowania.
Zmodyfikuj kazdy algorytm tak, aby zliczal liczbe porownan i zamian. Porownaj te wartosci dla listy posortowanej rosnaco, malejaco i losowej (kazda po 100 elementow). Ktory algorytm wykonuje najmniej operacji w kazdym przypadku?