BLOG.CYBERCRATE.PL

Kreatywnie o technologii

Sortowanie z pythonem

Sortowanie przez wstawianie i jego wizualizacja

Hej! Jest to pierwszy post na tym blogu o tematyce programowania. Ostatnio wpadły mi w ręce programy, które napisałem dawno, dawno temu, prawdopodobnie tak dawno, że przez ramię mógł mnie obserwować jakiś dinozaur. Miałem wtedy pomysł, aby kiedyś podzielić się z kimś tym kodem. Motywacją do jego stworzenia był sposób, w jaki na wykładach i prelekcjach opowiadano o algorytmach sortujących.Wydało mi się, że najprościej jest zobaczyć jak ten algorytm działa, a nie tylko teoretycznie rozważać jego sposób działania. Przyznam szczerze, że zapamiętanie nazwy do zasady działania, także przysporzyło mi kłopotu, więc postanowiłem sobie napisać program ściągę. Ten natomiast był zapisany w c++ z użyciem bibliotek graficznych…Troszkę bardziej skomplikowane, ale może kiedyś też się nim tutaj podzielimy.

Sortowanie przez wstawianie

No to do rzeczy! W tym artykule pokażę Wam sortowanie przez wstawianie. Ale bez strachu! Początkującym już tłumaczę o co w nim chodzi. Wyobraź sobie tabelkę z losowymi liczbami, albo lepiej: mamy kilka patyków o różnych długościach, jak poniżej… No dobra, może nie są one jakoś bardzo podobne do patyków, ale umówmy się, ja tu jestem od programowania, a nie rysowania 😉

Mamy już te prostokąty symbolizujące nasze patyki, teraz chcemy je posortować. Pomysł jest taki: bierzemy patyk i przesuwamy go w lewo, dopóki po lewej jest jakiś większy prostokąt. I to działa!!!

 Zauważ że pierwszego “patyka” nie przesuwamy, bo po lewej nie ma nic co jest większe, a każdy kolejny patyk gdy zostanie przesuniętyspowoduje, że coraz więcej patyków zostaje posortowanych. Biorąc każdy kolejny patyk “wstawimy” go we właściwe miejsce – stąd nazwa: sortowanie przez wstawianie.

 Pod spodem mała wizualizacja w formie filmu. P.S.Tak będzie wyglądała nasza gotowa aplikacja.

Pomarańczowy kolor, to miejsce z którego element został pobrany, natomiast na zielono zaznaczam element aktualnie przesuwany na miejsce.

Po pierwsze, wypada nam napisać na szybko sam kod odpowiadający za sortowanie, tak aby głębiej zrozumieć ten koncept. (Jeśli potrzebujesz kodu do zadania na studiach/w szkole, to poniżej Ci podpowiem jak to zrobić 😉 )

def sortowanie_wstawianie(tablica):
     for i in range(0,len(tablica)):
         j = i-1
         while(j>=0 and tablica[j]>tablica[j+1]):
             tablica[j], tablica[j+1] = tablica[j+1], tablica[j]
             j-=1
Kod jest w miarę prosty, ale tak dla pewności: pierwsza pętla wybiera element, który będziemy przesuwać – konkretnie bierze każdy element z naszej tablicy. Zmienna j odpowiada za wskazanie miejsca lądowania. Kolejna pętla zajmie się przesuwaniem – jeśli po lewej jest miejsce i element jest większy niż nasz, to przesuwamy.

Wizualizacja

Tak jak obiecywałem, przejdziemy teraz do wizualizacji. Poniżej kilka przydatnych linii kodu:

import pygame
#inicjalizacja
pygame.init()
#stworzenie powierzchni
surface = pygame.display.set_mode((<szerokość>,<wysokość>))
#stworzenie struktury z parametrami koloru
color = (<R>,<G>,<B>)
#przygotowanie prostokąta
rectangle = pygame.Rect(<lewa>, <góra>, <szerokość>, <wysokość>)
#rysowanie
pygame.draw.rect(surface, color, rectangle)
#zamiana ramki - wypchnięcie bufora na ekran
pygame.display.flip()

Warto tu powiedzieć jak to w ogóle się dzieje, że widzimy graficzne cudeńka na ekranie. Większość bibliotek implementuje koncept bufora. Konkretnie, zawsze gdy coś robimy,robimy to na buforze, a dopiero później mówimy bibliotece, aby zamieniła ramkę – pokazała zawartość bufora na ekranie. To właśnie robi funkcja flip pokazana powyżej.

 Już mamy trochę pojęcia o grafice, więc spróbujemy coś narysować. Po pierwsze wypełniamy ekran białym kolorem. Później trzeba troszku fancy matematyki żeby dobrze policzyć współrzędne i wysokości słupków. Następna jest pętla, która wyrysuje nam każdy słupek po kolei. W tym momencie musimy określić wymiary dla każdego słupka. Tworzymy obiekt prostokąta i rysujemy go na buforze. Po skończeniu rysowania wszystkich prostokątów, obracamy ramkę, aby pokazać efekt na ekranie.

def rysuj(tabela,szer,wys,surface):
     surface.fill((255, 255, 255))
     maksimum = max(tabela)
     wspolczynnik = wys//maksimum
     szerokosc_slupka = szer//len(tabela)
     for i in range(len(tabela)):
         color=(255,255,255)
         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()

A teraz szybkie wyjaśnienie, po co ta fancy matematyka – prostokąt konstruujemy podając współrzędne jego początku. Tylko tutaj uwaga, pułapka na początkujących! Punkt zero mamy w lewym górnym rogu, a współrzędne rosną w prawo i w dół. Dlatego właśnie potrzebne nam są te obliczenia – podajemy współrzędne lewego górnego rogu prostokąta, a następnie jego wymiary, które musimy jeszcze przeskalować tak, aby wszystkie prostokąty ładnie się pomieściły.

Kolejną rzeczą będzie dodanie integracji sortowania z rysowaniem

import pygame
from pygame.locals import *     #Zawiera stałą opisującą zdarzenie wyjścia

def eventHandling():
     for event in pygame.event.get():
         if event.type == QUIT:
             pygame.quit()
             return False
     return True
def rysuj(tabela,szer,wys,surface):
     eventHandling()
     surface.fill((255, 255, 255))
     maksimum = max(tabela)
     wspolczynnik = wys//maksimum
     szerokosc_slupka = szer//len(tabela)
     for i in range(len(tabela)):
         color=(255, 255, 255)
         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_wstawianie(tablica, szer, wys, surface, czekaj_ms):
     for i in range(0,len(tablica)):
         j = i-1
         while(j>=0 and tablica[j]>tablica[j+1]):
             tablica[j], tablica[j+1] = tablica[j+1], tablica[j]
             j-=1
             rysuj(tablica,szer,wys,surface)
             pygame.time.wait(czekaj_ms)

def run(tablica, szer, wys, czekaj_ms):
     pygame.init()
     surface = pygame.display.set_mode((szer,wys))
     sortowanie_wstawianie(tablica, szer, wys, surface, czekaj_ms)
     waiting = True
     while waiting:
         waiting=eventHandling()

eventHandling – Czyści i obsługuje kolejkę zdarzeń przesłanych do programu przez system operacyjny. Dzięki jego zastosowaniu program można zamknąć za pomocą krzyżyka, oraz nie zwiesi się on przy przenoszeniu okienka. Jest wywoływany przy każdym rysowaniu i w nieskończonej pętli.

run(tablica, szer, wys, czekaj_ms) – Funkcja uruchamiająca, pozwala ukryć część kodu, aby finalne uruchomienie było łatwiejsze

surface.fill((255, 255, 255)) – Przed każdym uruchomieniem rysowania czyści ekran, aby elementy się nie nakładały.

pygame.time.wait(czekaj_ms) – Powoduje wstrzymanie wykonania czynności na zadaną ilość milisekund. Nie wykorzystuje czasu procesora.

 Jeszcze jedna sztuczka zasługuje na objaśnienie:

wspolczynnik = wys//maksimum
szerokosc_slupka = szer//len(tabela)

Zastosowanie dzielenia całkowitego, pomaga uniknąć niechcianych odstępów między prostokątami.

Teraz dla lepszego zobrazowania kolejnych zdarzeń, zastosujemy kilka kolorków. Konkretnie, aby ułatwić sobie życie, napiszemy funkcję, która znając parametry – który słupek aktualnie przetwarzamy, skąd braliśmy słupek, oraz gdzie teraz jest wzięty słupek – poda nam kolor słupka o który pytamy.

def kolor(aktualny, i, j):
     if(aktualny == j):
         return (0,255,0)
     if(aktualny == i):
         return (255,165,0)
     return (0,0,0)

Teraz zostaje tylko dołożyć to do naszego kodu, co pokazuję poniżej:

import pygame
from pygame.locals import *
def eventHandling():
     for event in pygame.event.get():
         if event.type == QUIT:
             pygame.quit()
             return Falsese
     return True
def kolor(aktualny, i, j):
     if(aktualny == j):
         return (0,255,0)
     if(aktualny == i):
         return (255,165,0)
     return (0,0,0)
def rysuj(tabela,szer,wys,surface,pozycja_i,pozycja_j):
     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,pozycja_i,pozycja_j)
         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 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 sortowanie_wstawianie(tablica, szer, wys, surface, czekaj_ms):
     for i in range(0,len(tablica)):
         j = i-1
         while(j>=0 and tablica[j]>tablica[j+1]):
             tablica[j], tablica[j+1] = tablica[j+1], tablica[j]
             j-=1
             rysuj(tablica,szer,wys,surface,i,j+1)
             pygame.time.wait(czekaj_ms)

def run(tablica, szer, wys, czekaj_ms):
     pygame.init()
     surface = pygame.display.set_mode((szer,wys))
     sortowanie_wstawianie(tablica, szer, wys, surface, czekaj_ms)
     waiting = True
     while waiting:
         waiting=eventHandling()

Teraz abyśmy mogli rozkoszować się obrazkami, bez konieczności samodzielnego wymyślania danych, możemy stworzyć funkcję, która zrobi to za nas! Bo od czego jest komputer, jak nie od robienia tego czego nam się nie chce?

from random import randint
def randomArray(rozmiar, minimalna, maksymalna):
     wynik=[]
     for i in range(rozmiar):
         wynik.append(randint(minimalna,maksymalna))
     return wynik

Kolejną sprawą do opanowania jest pomiar czasu. Zobaczmy jak to zrealizować:

def wypiszCzas(surface, czas):  # Funkcja wypisująca czas na ekran
     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()

Tak aby wszystko zadziałało, musimy jeszcze wykonać pomiar czasu, w tym celu zmodyfikujemy funkcję uruchamiającą algorytm, oraz dodamy import:

def run(tablica, szer, wys, czekaj_ms):
     pygame.init()
     surface = pygame.display.set_mode((szer,wys))
     czas_start=time.time()
     sortowanie_wstawianie(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

Teraz pozostaje już tylko dodać funkcję dla totalnych leniwców, która zespoli nam wszystko!

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)

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 Falsese
     return True
def kolor(aktualny, i, j):
     if(aktualny == j):
         return (0,255,0)
     if(aktualny == i):
         return (255,165,0)
     return (0,0,0)
def rysuj(tabela,szer,wys,surface,pozycja_i,pozycja_j):
     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,pozycja_i,pozycja_j)
         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 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 sortowanie_wstawianie(tablica, szer, wys, surface, czekaj_ms):
     for i in range(0,len(tablica)):
         j = i-1
         while(j>=0 and tablica[j]>tablica[j+1]):
             tablica[j], tablica[j+1] = tablica[j+1], tablica[j]
             j-=1
             rysuj(tablica,szer,wys,surface,i,j+1)
             pygame.time.wait(czekaj_ms)

def run(tablica, szer, wys, czekaj_ms):
     pygame.init()
     surface = pygame.display.set_mode((szer,wys))
     czas_start=time.time()
     sortowanie_wstawianie(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,60,40,0,100)

Autor: Jakub Skrzyński
Korekta językowa: Wojciech Łyk

c++ 2 ciekawostki 2 DIY 2 do egzaminu 2 do matury 2 programowanie 4 projekt 2 pygame 2 python 2 sortowanie 2 sortowanie bąbelkowe 1 sortowanie przez wstawianie 1 std c++ 1 sztuczki 2 tutorial 2 wizualizacja 2
A to może Cię zainteresować...
Scroll to Top