BLOG.CYBERCRATE.PL
Kreatywnie o technologii
Sortowanie z pythonem
Sortowanie bąbelkowe i jego wizualizacja
W drugim już artykule z serii o sortowaniu, chciałbym zaznajomić Cię z kolejnym rodzajem sortowania – sortowaniem bąbelkowym. Legenda którą kiedyś usłyszałem, głosi, że nazwa wywodzi się od bąbelków w złocistym gazowanym napoju, bowiem jak owa legenda głosi, bąbelki większe wypływają szybciej do góry, a w tym algorytmie wygląda to podobnie. Będziemy zamieniali elementy tak, że będzie wyglądało to jakby największe wypływały na powierzchnię.
Zainteresowanych tematem odsyłąm również do pierwszego artykułu z tej serii
Algorytm - sortowanie bąbelkowe
Spróbuję wytłumaczyć to w podobnie prosty sposób jak w poprzednim artykule. Wyobraźmy sobie, że na stole układamy, w linii, kartoniki z liczbami. Teraz, korzystając z dwóch rąk, rozpoczynamy sortowanie. Lewą rękę kładziesz na pierwszym kartoniku, a prawą na drugim. Podnosisz kartoniki i porównujesz czy, są we właściwej kolejności, jeśli nie – zamieniasz je miejscami i odkładasz, jeśli są w dobrej – po prostu odkładasz. Teraz przesuwasz się o jeden kartonik w prawo – lewa ręka wędruje na drugi kartonik, a prawa na trzeci i ponownie porównujemy. Robimy tak, aż nie dojdziemy prawą ręką do ostatniego kartonika. Teraz patrząc na tą linię kartoników, możemy zauważyć, że jeden jest już na pewno na swoim miejscu – ostatni. Możemy więc kontynuować naszą zabawę – zaczynamy od początku, lewa ręka na pierwszy, a prawa na drugi i porównujemy. Tylko tym razem zakończymy, nie gdy prawa ręka wyląduje na ostatnim, a na przedostatnim. Dlaczego? Odpowiedź jest dość prosta – ostatni jest już posortowany i “zapominamy o nim”. Gdy i tą rundę zakończymy, kolejna odbędzie się w bardzo podobny sposób. Kiedy skończymy? Proste! Ostatnia runda będzie wyglądała tak, że mamy dwa elementy – zamieniamy je, albo nie. Ostatniego nie ma co sortować, bo jak można zauważyć, jeden element jest zawsze posortowany.
No to teraz tylko szybki pomysł jak to zrobić, aby fajnie to w komputerze wyglądało – tak jak poprzednio do zobrazowania wartośc liczbowych, użyjemy słupków o różnych wysokościach. Poniżej również szybka animacja, tak aby zobaczyć jak to działa.
Kod w pythonie - sortowanie bąbelkowe
def sortowanie_babelkowe(tablica):
n = len(tablica)
for i in range(n): #ile elementów jest już posortowanych
for j in range(n-i-1):
print(tablica) # wizualizacja dla debugowania
itA = j # iterator A
itB = j+1 # iterator B
#print(f"Porównanie pary: tablica[{itA}] = {tablica[itA]}, tablica[{itB}] = {tablica[itB]}")
if tablica[itA]>tablica[itB]: # elementy nieprawidłowe - zamiana
tablica[itA],tablica[itB] = tablica[itB],tablica[itA]
print(tablica) # wizualizacja dla debugowania
print("Posortowano", i+1, "elementów")
print(tablica) # wizualizacja dla debugowaniaMuszę się przyznać, że napisałem ten kod przed wymyśleniem analogii z rękoma, a więc chyba czas to troszeczkę przepisać, aby łatwiej było patrzeć na niego. Poniżej prezentuję owoc kilku minut pracy – wydaje mi się że dużo czytelniejszy dla początkujących i w 100% kompatybilny z opisem powyżej 😉
def sortowanie_babelkowe(tablica):
n = len(tablica)
posortowane = 0
lewa = 0
prawa = 0
while n-posortowane > 1:
lewa = 0
prawa = 1
ostatni = n-posortowane-1
# -1 powyżej jest dladego, że iteretory liczymy od zera
print(tablica) # wizualizacja dla debugowania
while prawa<=ostatni:
#print(f"Porównanie pary: tablica[{lewa}] = {tablica[lewa]}, tablica[{prawa}] = {tablica[prawa]}")
if tablica[lewa] > tablica[prawa]:
tablica[lewa], tablica[prawa] = tablica[prawa], tablica[lewa]
lewa+=1
prawa+=1
print(tablica) # wizualizacja dla debugowania
posortowane+=1
print("Posortowano", posortowane, "elementów")
print(tablica) # wizualizacja dla debugowaniaPod spodem, dorzucam jeszcze obrazek z tego jak ten kod działa. Tak na marginesie, widać że python nie umie polskiego 😀 na 4 próby, w 4 nie radzi sobie z odmianą “końcówków”
>>> sortowanie_babelkowe_2([5,4,3,2,1])
[5, 4, 3, 2, 1]
[4, 5, 3, 2, 1]
[4, 3, 5, 2, 1]
[4, 3, 2, 5, 1]
[4, 3, 2, 1, 5]
Posortowano 1 elementów
[4, 3, 2, 1, 5]
[3, 4, 2, 1, 5]
[3, 2, 4, 1, 5]
[3, 2, 1, 4, 5]
Posortowano 2 elementów
[3, 2, 1, 4, 5]
[2, 3, 1, 4, 5]
[2, 1, 3, 4, 5]
Posortowano 3 elementów
[2, 1, 3, 4, 5]
[1, 2, 3, 4, 5]
Posortowano 4 elementów
[1, 2, 3, 4, 5]Trzeba jednak przyznać, że pierwszy kod jest troszkę krótszy, ale mimo to, dla lepszego zobrazowania jak wizualizacja algorytmu sortowania bąbelkowego jest realizowana w pygame, będę rzymał się drugiej implementacji. I tutaj warto też zauważyć, bardzo, ale to bardzo ważną rzecz – programu nie uczymy się na pamięć! Nawet tutaj, gdzie algorytm jest jasno określony, możemy napisać go na bardzo wiele sposobów, dlatego też nauczyć się możemy jedynie składni języka i jakichś sztuczek, ale płynność w posługiwaniu się nim, czyli pisaniu programów, musimy wypracować. I tutaj niestety jest jedna droga – pisać, pisać i jeszce raz pisać, popatrzeć na kod kogoś innego, nabrać inspiracji, pisać, pisać i jeszcze raz pisać.
Wizualizacja - pygame i sortowanie bąbelkowe
Elementy kodu wykorzystamy z poprzedniego projektu. O nich napiszę tylko kilka słów, dla ciekawskich, pozostawiam link do poprzedniego artykułu w którym te elementy zostały dokładniej opisane.
To zaczynamy standardowo od importów, takich jak w ostatnim programie, oraz funkcji która nas uratuje przed zawieszaniem się programu przy interakcji z okienkiem pygame.
import pygame
from pygame.locals import *
from random import randint
import time
def eventHandling():
for event in pygame.event.get():
if event.type == QUIT:
pygame.quit()
return False
return TrueLubię sobie ułatwiać życie, więc dodam jeszcze enum, który określi mi aktualny stan naszej wizualizacji
class Stan(Enum):
Zwykly = 1
Zmiana = 2 # Zamieniamy miejscami
Ok = 3 # Kolejność jest okKolejna rzecz, to funkcja determinująca kolor słupka, na podstawie pozycji “rąk”, oraz stanu wizualizacji
def kolor(i,lewa,prawa,stan: Stan):
kolorLewa = (255,165,0)
kolorPrawa = (255,165,0)
kolorZamiana = (255,0,0)
kolorOk = (0,255,0)
kolorZwykle = (0,0,0)
if stan == Stan.Zmiana and (i == lewa or i == prawa):
return kolorZamiana
if stan == Stan.Ok and (i == lewa or i == prawa):
return kolorOk
if i == lewa:
return kolorLewa
if i == prawa:
return kolorPrawa
return kolorZwykleKolejny element, to funkcja rysująca. Weźmiemy tą samą co w poprzednim projekcie i przystosujmy do nowego zadania
def rysuj(tabela,szer,wys,surface,lewa,prawa,stan):
eventHandling()
surface.fill((255, 255, 255))
maksimum = max(tabela)
wspolczynnik = wys//maksimum
szerokosc_slupka = szer//len(tabela)
for i in range(len(tabela)):
color=kolor(i,lewa,prawa,stan)
wartosc = tabela[i]
wysokosc_slupka = wartosc*wspolczynnik
margines_gorny = wys-wysokosc_slupka
margines_lewy = szerokosc_slupka*i
rectangle = pygame.Rect(margines_lewy,margines_gorny,szerokosc_slupka,wysokosc_slupka)
pygame.draw.rect(surface, color, rectangle)
pygame.display.flip()
Okazuje się, że zbyt wiele zmian nie było tutaj koniecznych. Kolejnym krokiem będzie połączenie funkcji sortującej z funkcją rysującą.
def sortowanie_babelkowe(tablica,szer,wys,surface, czekaj_ms):
n = len(tablica)
posortowane = 0
lewa = 0
prawa = 0
while n-posortowane > 1:
lewa = 0
prawa = 1
ostatni = n-posortowane-1
while prawa<=ostatni:
rysuj(tablica,szer,wys,surface,lewa,prawa,Stan.Zwykly)
pygame.time.wait(czekaj_ms)
if tablica[lewa] > tablica[prawa]:
rysuj(tablica,szer,wys,surface,lewa,prawa,Stan.Zmiana)
pygame.time.wait(czekaj_ms)
tablica[lewa], tablica[prawa] = tablica[prawa], tablica[lewa]
rysuj(tablica,szer,wys,surface,lewa,prawa,Stan.Ok)
pygame.time.wait(czekaj_ms)
else:
rysuj(tablica,szer,wys,surface,lewa,prawa,Stan.Ok)
pygame.time.wait(czekaj_ms)
lewa+=1
prawa+=1
posortowane+=1
rysuj(tablica,szer,wys,surface,lewa,prawa,Stan.Zwykly)Następnym elementem, będzie przygotowanie wrappera wszystkich procedur potrzebnych do uruchomienia naszego programu i obliczania czasu działania sortowania. Wrappera oraz jeszcze jedną funkcję – odpowiedzialną za wypisanie czasu działania, zapożyczymy również z poprzedniego projektu.
def wypiszCzas(surface, czas):
font = pygame.font.Font(pygame.font.get_default_font(), 15)
color=(255,0,0)
text_surface = font.render("Czas wykonania: "+str(round(czas,6)), True, color)
surface.blit(text_surface, dest=(10,10))
pygame.display.flip()
def run(tablica, szer, wys, czekaj_ms):
pygame.init()
surface = pygame.display.set_mode((szer,wys))
czas_start=time.time()
sortowanie_babelkowe(tablica, szer, wys, surface, czekaj_ms)
czas_stop=time.time()
czas=czas_stop-czas_start
wypiszCzas(surface,czas)
waiting = True
while waiting:
waiting=eventHandling()
return czasOstatni element, to tak jak poprzednio, funkcje dla leniwców – losowa tablica i opakowanie całości
def randomArray(rozmiar, minimalna, maksymalna):
wynik=[]
for i in range(rozmiar):
wynik.append(randint(minimalna,maksymalna))
return wynik
def sortujLosowaTablice(szer_okna, wys_okna, czekaj_ms, ilosc_elementow, minimalny, maksymalny):
return run(randomArray(ilosc_elementow, minimalny, maksymalny),szer_okna, wys_okna, czekaj_ms)
sortujLosowaTablice(400,400,60,40,0,100)I tak właśnie prezentuje się nasz piękny, gotowy kod:
import pygame
from pygame.locals import *
from random import randint
import time
def eventHandling():
for event in pygame.event.get():
if event.type == QUIT:
pygame.quit()
return False
return True
from enum import Enum
class Stan(Enum):
Zwykly = 1
Zmiana = 2
Ok = 3
def kolor(i,lewa,prawa,stan: Stan):
kolorLewa = (255,165,0)
kolorPrawa = (255,165,0)
kolorZamiana = (255,0,0)
kolorOk = (0,255,0)
kolorZwykle = (0,0,0)
if stan == Stan.Zmiana and (i == lewa or i == prawa):
return kolorZamiana
if stan == Stan.Ok and (i == lewa or i == prawa):
return kolorOk
if i == lewa:
return kolorLewa
if i == prawa:
return kolorPrawa
return kolorZwykle
def rysuj(tabela,szer,wys,surface,lewa,prawa,stan):
eventHandling()
surface.fill((255, 255, 255))
maksimum = max(tabela)
wspolczynnik = wys//maksimum
szerokosc_slupka = szer//len(tabela)
for i in range(len(tabela)):
color=kolor(i,lewa,prawa,stan)
wartosc = tabela[i]
wysokosc_slupka = wartosc*wspolczynnik
margines_gorny = wys-wysokosc_slupka
margines_lewy = szerokosc_slupka*i
rectangle = pygame.Rect(margines_lewy,margines_gorny,szerokosc_slupka,wysokosc_slupka)
pygame.draw.rect(surface, color, rectangle)
pygame.display.flip()
def sortowanie_babelkowe(tablica,szer,wys,surface, czekaj_ms):
n = len(tablica)
posortowane = 0
lewa = 0
prawa = 0
while n-posortowane > 1:
lewa = 0
prawa = 1
ostatni = n-posortowane-1
while prawa<=ostatni:
rysuj(tablica,szer,wys,surface,lewa,prawa,Stan.Zwykly)
pygame.time.wait(czekaj_ms)
if tablica[lewa] > tablica[prawa]:
rysuj(tablica,szer,wys,surface,lewa,prawa,Stan.Zmiana)
pygame.time.wait(czekaj_ms)
tablica[lewa], tablica[prawa] = tablica[prawa], tablica[lewa]
rysuj(tablica,szer,wys,surface,lewa,prawa,Stan.Ok)
pygame.time.wait(czekaj_ms)
else:
rysuj(tablica,szer,wys,surface,lewa,prawa,Stan.Ok)
pygame.time.wait(czekaj_ms)
lewa+=1
prawa+=1
posortowane+=1
rysuj(tablica,szer,wys,surface,lewa,prawa,Stan.Zwykly)
def wypiszCzas(surface, czas):
font = pygame.font.Font(pygame.font.get_default_font(), 15)
color=(255,0,0)
text_surface = font.render("Czas wykonania: "+str(round(czas,6)), True, color)
surface.blit(text_surface, dest=(10,10))
pygame.display.flip()
def run(tablica, szer, wys, czekaj_ms):
pygame.init()
surface = pygame.display.set_mode((szer,wys))
czas_start=time.time()
sortowanie_babelkowe(tablica, szer, wys, surface, czekaj_ms)
czas_stop=time.time()
czas=czas_stop-czas_start
wypiszCzas(surface,czas)
waiting = True
while waiting:
waiting=eventHandling()
return czas
def randomArray(rozmiar, minimalna, maksymalna):
wynik=[]
for i in range(rozmiar):
wynik.append(randint(minimalna,maksymalna))
return wynik
def sortujLosowaTablice(szer_okna, wys_okna, czekaj_ms, ilosc_elementow, minimalny, maksymalny):
return run(randomArray(ilosc_elementow, minimalny, maksymalny),szer_okna, wys_okna, czekaj_ms)
sortujLosowaTablice(400,400,90,40,0,100)
Autor: Jakub Skrzyński
Korekta językowa: Wojciech Łyk
