Lekcja obowiązkowa
Wskazówka do pracy: najpierw przewiń całą stronę, żeby się zorientować, jakie elementy zawiera, a dopiero potem zacznij pracować.
W czasie trwania lekcji – w środy o godz. 11.50 – odpowiem na Twoje pytania na bieżąco (możesz skorzystać z poczty elektronicznej, Facebooka, Messengera lub wpisać komentarz pod lekcją).
Możesz się ze mną skontaktować także w innym terminie – odpowiem najszybciej, jak to będzie możliwe.
Temat: Algorytmy sortowania (porządkowania) – kolejne przykłady
Jeśli nie zrealizowałaś/zrealizowałeś w poprzedniej lekcji – koniecznie nadrób zaległości (kliknij).
Realizując poprzednią lekcję, poznałaś/poznałeś dwa algorytmy sortowania (porządkowania) danych, a na dzisiejszej lekcji poznasz… jeszcze kilka 🙂
Dlaczego poświęcamy tyle czasu algorytmom sortowania? – Dlatego że należą one do najczęściej wykorzystywanych algorytmów w programowaniu.
Różnią się od siebie między innymi złożonością (zależnością liczby wykonanych operacji w stosunku od liczebności sortowanego zbioru) i sposobem działania.
Sortowanie bąbelkowe (bubblesort)
To jeden z najprostszych algorytmów porządkujących.
Stosując ten algorytm podczas porządkowania np. tablicy zawierającej przypadkowo rozmieszczone liczby, które chcemy uporządkować rosnąco (czyli od najmniejszej liczby do największej) – „przechodzimy” od początku tablicy do jej końca i porównujemy dwie sąsiednie liczby. Jeżeli pierwsza liczba jest większa od drugiej, to zamieniamy je miejscami.
Po pierwszym „przejściu” wykonujemy kolejne itd.
Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonujemy żadnej zmiany.
Jeżeli obejrzysz poniższy film, to zobaczysz występ węgierskiego zespołu ludowego, którego członkowie pokazują tańcem, jak realizowany jest algorytm sortowania bąbelkowego 😉
Algorytm nosi nazwę bąbelkowego, ponieważ przypomina przemieszczanie się bąbelków w wodzie, ku górze.
Sortowanie przez wstawianie (Insert Sort, Insertion Sort)
Metoda ta polega na układaniu kolejnych elementów poprzez wstawianie ich we właściwe miejsce, co przypomina układanie kart do gry w dłoni, kiedy każdą kartę umieszczamy w odpowiednim miejscu, tzn. po młodszej, ale przed starszą.
Stosując ten algorytm w celu uporządkowania jakiegoś zbioru elementów (np. przypadkowych liczb) – dzielimy zbiór na dwie części: część uporządkowaną (początkowo pustą) i część nieuporządkowaną (zawierającą początkowo wszystkie elementy zbioru, który chcemy uporządkować).
Zaczynamy od przeniesienia dowolnie wybranego elementu z części nieuporządkowanej do części posortowanej.
Potem kolejny element przenosimy z części nieuporządkowanej do części uporządkowanej i porównujemy go ze znajdującym się tam elementem – oba ustawiamy we właściwej kolejności.
Następnie kolejny element przenosimy z części nieuporządkowanej do części uporządkowanej i porównujemy go z kolejnymi elementami zbioru uporządkowanego, dopóki nie trafi we właściwe miejsce.
Podobnie postępujemy z kolejnymi elementami.
Algorytm zostaje zakończony, gdy wszystkie elementy znajdą się w zbiorze uporządkowanym.
Taneczną ilustrację działania tego algorytmu możesz zobaczyć na poniższym filmie 😉
Sortowanie przez scalanie (merge sort)
Stosując ten algorytm w celu uporządkowania jakiegoś zbioru elementów (np. przypadkowych liczb), zaczynamy od podzielenia danego zbioru na mniejsze zbiory (najpierw dzielimy zbiór na dwie części, potem każdą z tych części na kolejne dwie itd.), aż do uzyskania zbiorów jednoelementowych (które są – oczywiście – posortowane).
Następnie kolejno łączymy zbiory jednoelementowe w dwuelementowe – ustawiając ich elementy we właściwej kolejności; a potem dwuelementowe w czteroelementowe – znowu ustawiając ich elementy we właściwej kolejności… itd.
Algorytm zostaje zakończony, gdy wszystkie mniejsze zbiory zostaną połączone, a ich elementy – posortowane
Poniżej – taneczna wizualizacja działania tego algorytmu 😉
Zadanie
Który ze znanych Ci algorytmów sortowania został poniżej zilustrowany graficznie?
Podaj odpowiedź w komentarzu – nie zapomnij się podpisać 🙂
Komentarze są moderowane, więc nie martw się – nikt nie zobaczy Twoich danych (nie opublikuję ich, tylko zobaczę) ?
Jeśli masz jakieś pytania – napisz do mnie na adres info.tyka@gmail.com, skontaktuj się za pośrednictwem Messengera albo napisz komentarz pod tą lekcją.
