Sortowanie babelkowe, przez wstawianie, przez wybieranie - implementacja w Pythonie
ð Podstawa programowa: II.1+I.2cSortowanie to jeden z najwazniejszych problemow informatyki. Posortowane dane pozwalaja na szybkie wyszukiwanie (np. wyszukiwanie binarne), latwe znajdowanie minimum/maksimum i przejrzyste prezentowanie informacji.
Porownujemy kolejne pary sasiadujacych elementow i zamieniamy je, jesli sa w zlej kolejnosci. Powtarzamy az lista bedzie posortowana.
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 - jesli brak zamian, lista posortowana
break
return lista
dane = [64, 34, 25, 12, 22, 11, 90]
print(sortowanie_babelkowe(dane)) # [11, 12, 22, 25, 34, 64, 90]Bierzemy kolejne elementy i wstawiamy je na wlasciwe miejsce w juz posortowanej czesci listy.
def sortowanie_wstawianie(lista):
for i in range(1, len(lista)):
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
dane = [64, 34, 25, 12, 22, 11, 90]
print(sortowanie_wstawianie(dane)) # [11, 12, 22, 25, 34, 64, 90]Znajdujemy minimum w nieposortowanej czesci i zamieniamy je z pierwszym elementem tej czesci.
def sortowanie_wybieranie(lista):
n = len(lista)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if lista[j] < lista[min_idx]:
min_idx = j
lista[i], lista[min_idx] = lista[min_idx], lista[i]
return lista
dane = [64, 34, 25, 12, 22, 11, 90]
print(sortowanie_wybieranie(dane)) # [11, 12, 22, 25, 34, 64, 90]sort() - uzywa algorytmu TimSort (hybrydowy), zlozonosc O(n log n)Zaimplementuj sortowanie babelkowe z wyswietlaniem stanu listy po kazdym przebiegu petli zewnetrznej. Przetestuj dla listy [5, 3, 8, 1, 9, 2].
def sortowanie_babelkowe_viz(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"Przebieg {i+1}: {lista}")
return lista
sortowanie_babelkowe_viz([5, 3, 8, 1, 9, 2])Zaimplementuj wszystkie trzy algorytmy sortowania. Kazdy powinien zliczac liczbe porownan i zamian. Porownaj wyniki dla tej samej listy losowej (10 elementow).
import random
def babelkowe_stat(lista):
lista = lista.copy()
porownania = zamiany = 0
n = len(lista)
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_stat(lista):
lista = lista.copy()
porownania = zamiany = 0
for i in range(1, len(lista)):
klucz = lista[i]
j = i - 1
while j >= 0:
porownania += 1
if lista[j] > klucz:
lista[j + 1] = lista[j]
zamiany += 1
j -= 1
else:
break
lista[j + 1] = klucz
return porownania, zamiany
def wybieranie_stat(lista):
lista = lista.copy()
porownania = zamiany = 0
n = len(lista)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
porownania += 1
if lista[j] < lista[min_idx]:
min_idx = j
if min_idx != i:
lista[i], lista[min_idx] = lista[min_idx], lista[i]
zamiany += 1
return porownania, zamiany
dane = [random.randint(1, 100) for _ in range(10)]
print(f"Dane: {dane}\n")
p, z = babelkowe_stat(dane)
print(f"Babelkowe: porownania={p}, zamiany={z}")
p, z = wstawianie_stat(dane)
print(f"Wstawianie: porownania={p}, zamiany={z}")
p, z = wybieranie_stat(dane)
print(f"Wybieranie: porownania={p}, zamiany={z}")Zmodyfikuj sortowanie przez wstawianie tak, aby sortowalo malejaco. Dodaj parametr rosnaco=True aby moc wybrac kierunek sortowania.
def sortowanie_wstawianie(lista, rosnaco=True):
lista = lista.copy()
for i in range(1, len(lista)):
klucz = lista[i]
j = i - 1
if rosnaco:
while j >= 0 and lista[j] > klucz:
lista[j + 1] = lista[j]
j -= 1
else:
while j >= 0 and lista[j] < klucz:
lista[j + 1] = lista[j]
j -= 1
lista[j + 1] = klucz
return lista
dane = [5, 3, 8, 1, 9, 2]
print(f"Rosnaco: {sortowanie_wstawianie(dane, True)}")
print(f"Malejaco: {sortowanie_wstawianie(dane, False)}")Uzyj modulu time do zmierzenia czasu sortowania babelkowego i wbudowanego sort() dla list o rozmiarach 1000, 5000, 10000 elementow. Wyswietl wyniki w tabeli.
import random
import time
def sort_babelkowe(lista):
lista = lista.copy()
n = len(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]
return lista
rozmiary = [1000, 5000, 10000]
print(f"{'Rozmiar':>10} | {'Babelkowe':>12} | {'sort()':>12}")
print("-" * 40)
for n in rozmiary:
dane = [random.randint(1, 100000) for _ in range(n)]
start = time.time()
sort_babelkowe(dane)
czas_babel = time.time() - start
start = time.time()
sorted(dane)
czas_sort = time.time() - start
print(f"{n:>10} | {czas_babel:>10.4f}s | {czas_sort:>10.6f}s")