Sortowanie elementów listy

R1SNCDnUer0E3

bg‑gray4

Treści zawarte w tym e‑materiale wykraczają poza podstawę programową. Jeśli jednak:

interesujesz się informatyką i programowaniem,
chcesz dowiedzieć się więcej i poznać algorytm sortowania przez wybieranie,
podjąć próbę zapisania go w języku Scratch,

zachęcamy Cię do zapoznania się z tym e‑materiałem.

Sortowanie to jeden z podstawowych problemów informatycznych. Istnieje wiele algorytmów sortowania, jedne działają szybciej, inne wolniej. W tym podrozdziale poznasz jeden z nich: sortowanie przez wybieranie.

Naszym zadaniem jest uporządkowanie liczb znajdujących się na liście. Liczby mają być ustawione od najmniejszej do największej, a więc w pierwszym kroku można znaleźć liczbę najmniejszą i zamienić ją z pierwszym elementem listy. W kolejnym kroku postępujemy analogicznie, poszukując liczby najmniejszej, poczynając od drugiego elementu, następnie od trzeciego itd. Powtarzamy więc wybieranie i ustawianie liczby najmniejszej $n - 1$ razy (jak zostaje jedna liczba, to znajduje się już na właściwym miejscu, ciąg złożony z jednego elementu jest uporządkowany).

Przykład 1

W poniższym filmie przedstawiono kolejne kroki porządkowania następującego zestawu liczb: $8$ , $5$ , $1$ , $9$ , $3$ . Kolorem zielonym zaznaczone są liczby już ustawione, kolorem żółtym kolejne znalezione minimum, a czerwonym miejsce, na którym zostanie ustawione.

REHJjrBB8hYYO

Sortowanie przez wybieranie
Źródło: Janusz Wierzbicki, Maciej Borowiecki, licencja: CC BY-SA 3.0.

Zapis algorytmu sortowania przez wybieranie w postaci listy kroków:

Dane:
$n$ – liczba elementów listy,
$L$ – lista liczb.

Wynik:
$L$ – uporządkowana niemalejąco lista liczb.

Powtarzaj dla kolejnych wartości zmiennej $i$ od $1$ do $n - 1$ :
1.1. Ustaw wartość zmiennej $m$ na $i$ .
1.2. Powtarzaj dla kolejnych wartości zmiennej $j$ od $i + 1$ do $n$ :
⠀1.2.1. Jeżeli element na pozycji $j$ w $L$ $<$ element na pozycji $m$ w $L$ to ustaw wartość zmiennej $m$ na $j$ .
1.3. Zamień element na pozycji $i$ w $L$ z elementem na pozycji $m$ w $L$ .

Ćwiczenie 1

Utwórz skrypt (nowy blok) sortujący listę o nazwie Odcinki zgodnie z algorytmem przez wybieranie. Pamiętaj o utworzeniu wszystkich niezbędnych zmiennych.

Przykładowy skrypt:

Zmienne:

$p o m$ – zmienna pomocnicza do przechowywania wartości mniejszego odcinka,
$i$ – licznik iteracji dla pierwszej pętli,
$j$ – licznik iteracji dla zagnieżdżonej pętli.

R1LrAUX6oyyeR

Zrzut ekranu przedstawia skrypt sortujący listę odcinków. Zaczyna się on od elementu z napisem definiuj sortowanie, następnie znajduje się blok, który odpowiada za ustawienie zmiennej i jako wartość jeden. Poniżej jest element, który jest odpowiedzialny za powtarzanie pierwszej pętli dopóki i jest większe od długości listy odcinków. Wewnątrz tej pętli najpierw zmienna sortowanie jest ustawiana na wartość zmiennej i oraz zmienna j jest ustawiana na wartość zmiennej i. Następnie powtarzana jest pętla, dopóki zmienna j jest większa od długości listy odcinków, w której jest blok z napisem jeżeli element j z listy odcinków jest mniejszy od elementu sortowanie z listy odcinków, to zmienna sortowanie ustawiana jest na j. Zmienna j jest zwiększana o jeden. Po wykonaniu tej pętli zmienna pom ustawiana jest na element i z listy odcinków. Element i z listy odcinków zamieniany jest na element sortowanie z listy odcinków, a element sortowanie z listy odcinków zamieniany jest na zmienną pom. Zmienna i zwiększana jest o jeden i pierwsza pętla jest powtarzana. Na dole jest blok z napisem zatrzymaj ten skrypt, który kończy skrypt. — Przykładowa definicja bloku sortowanie
Źródło: GroMar Sp. z o.o., licencja: CC BY-SA 3.0.

Rcs5dAouaBH0U

Ćwiczenie 1

Źródło: GroMar Sp. z o.o., licencja: CC BY-SA 3.0.

Na pierwszej stronie tego materiału tworzyliśmy aplikację, w której losowana jest lista liczb, następnie duszek poprosi o podanie liczby i sprawdza, czy ona występuje na liście. Ponownie zajmiemy się tym zadaniem, ale teraz zanim wyszukamy element posortujemy listę.

Ćwiczenie 2

Przygotuj aplikację, w której losowana jest lista liczb. Następnie niech duszek posortuj listę, poprosi o podanie liczby, a następnie sprawdzi czy jest ona na liście. Zastanów się, czy wyszukując liczbę w posortowanej liście, można zastosować algorytm, który wykona mniej operacji niż przeszukiwanie listy element po elemencie.

Uruchom poniższą aplikację, w której duszek zgaduje liczbę pomyślaną przez ciebie. Postaraj się wykorzystać algorytm stosowany przez duszka w rozwiązaniu ćwiczenia.

RpuhjReNf8S2v

Aplikacja zgadująca liczbę pomyślaną przez użytkownika
Źródło: Janusz Wierzbicki, Maciej Borowiecki, licencja: CC BY-SA 3.0.

Interaktywna gra, w której duszek zgaduje wybraną przez Ciebie liczbę.
Znajdź informację o metodzie dziel i zwyciężaj w internecie lub innych źródłach. Dzięki niej można szybko sprawdzić, czy poszukiwana liczba znajduje się na posortowanej liście.
Gra interaktywna. Po wybraniu, w lewym górnym rogu, przycisku z napisem uruchom, rozpoczyna się gra. Nad postacią duszka wyświetla się okno dialogowe z napisem: pomyśl liczbę całkowitą od 1 do 100, a ja zgadnę! Naciśnij przycisk, jak będziesz gotowy. W górnym lewym rogu pojawia się niebieski przycisk z napisem: zgaduj. Po naciśnięciu niebieskiego przycisku pojawia się nowe okno dialogowe z napisem: czy Twoja liczba to $50$ . Na górze, od lewej strony, znajdują się kolejno trzy niebieskie przyciski: jest mniejsza, tak, jest większa.
W przypadku wybrania przycisku: tak w oknie dialogowym pojawia się komunikat: zgadłem! Twoja liczba to $50$ . W lewym górnym rogu pojawia się przycisk z napisem: uruchom, grę można rozpocząć od nowa.
W przypadku wybrania przycisku z napisem: jest mniejsza w oknie dialogowym nad duszkiem pojawia się nowy komunikat: czy Twoja liczba to $25$ . W przypadku ponownego wybierania przycisku z napisem: jest mniejsza w oknie dialogowym pojawia się napis z kolejno obniżoną wartością liczbową: czy Twoja liczba to $12$ , $6$ , $3$ , $1$ . Po wyświetleniu ostatniego komunikatu w oknie dialogowym pojawia się napis: udzielasz sprzecznych odpowiedzi. Grę można rozpocząć od nowa.
W przypadku wybrania przycisku z napisem: jest większa w oknie dialogowym nad duszkiem pojawia się nowy komunikat: czy Twoja liczba to $75$ . W przypadku ponownego wybierania przycisku z napisem: jest większa w oknie dialogowym pojawia się napis z kolejno podwyższoną wartością liczbową: czy Twoja liczba to $88$ , $94$ , $97$ , $99$ . Po wyświetleniu ostatniego komunikatu w oknie dialogowym pojawia się napis: wiem! Twoja liczba to $100$ . Grę można rozpocząć od nowa.

Przykładowe skrypty

R1cWOLttOn6ql

Zrzut ekranu przedstawia przykładowy skrypt losowania liczb i sprawdzania, czy podana liczba się w nich znajduje, z wykorzystaniem bloku dziel_zwyciezaj. Skrypt rozpoczyna się od elementu z napisem kiedy kliknięto z ikoną zielonej flagi. Poniżej jest blok z napisem usuń wszystko z Odcinki, co oznacza usunięcie wszystkiego z listy odcinków. Następnie znajduje się element, który wydaje polecenie o powtórzeniu czynności dziesięć razy, do niego dołączono blok, który odpowiada za losowanie liczby z zakresu od jednego do dziesięciu i dodanie jej do listy odcinków. Poniżej jest blok z napisem sortowanie, a do niego przylega element z napisem zapytaj i czekaj oraz pytaniem: Podaj liczbę, a ja sprawdzę, czy występuje na liście. Do tych elementów dołączono blok z napisem dziel_zwyciezaj odpowiedź zero długość Odcinki. Na dole jest element z napisem zatrzymaj ten skrypt, który kończy skrypt. — Przykładowy skrypt losowania liczb i sprawdzania, czy podana liczba się w nich znajduje, z wykorzystaniem bloku dziel_zwyciezaj
Źródło: GroMar Sp. z o.o., licencja: CC BY-SA 3.0.

RuBZm3wyjVAMV

Zrzut ekranu przedstawia przykładową definicję bloku sortowanie. Zaczyna się on od elementu z napisem definiuj sortowanie, następnie znajduje się blok, który odpowiada za ustawienie zmiennej i jako wartość jeden. Poniżej jest element, który jest odpowiedzialny za powtarzanie pierwszej pętli, dopóki i jest większe od długości listy odcinków. Wewnątrz tej pętli zmienna j jest ustawiana na wartość zmiennej i. Następnie powtarzana jest pętla, dopóki zmienna j jest większa od długości listy odcinków, w której jest blok z napisem: jeżeli element j z listy odcinków jest mniejszy od elementu i z listy odcinków, to zmienna pom ustawiana jest na element i z Odcinki. Element i z listy odcinków zamieniany jest na element j z listy odcinków, a element j z listy odcinków zamieniany jest na zmienną pom. Następnie zmienna j zwiększa się o jeden. Dalej zmienna i zwiększa się o jeden. Na dole jest blok z napisem zatrzymaj ten skrypt, który kończy skrypt. — Przykładowa definicja bloku sortowanie
Źródło: GroMar Sp. z o.o., licencja: CC BY-SA 3.0.

RRbqQiYmsfPcT

Zrzut ekranu przedstawiający przykładową definicję bloku dziel_zwyciezaj. Skrypt rozpoczyna się od bloku z napisem definiuj dziel_zwyciezaj, liczba, początek_listy, koniec_listy. W kolejnym elemencie, jeżeli początek listy jest mniejszy od końca listy lub początek listy jest jej równy, to zaokrąglony wynik dzielenia przez dwa sumy początku i końca listy. Następny blok dotyczy równania: jeżeli zmienna liczba jest równa elementowi środek z listy odcinków, to występuje komunikat Tak, podana liczba znajduje się na liście. Do tego elementu dołączony jest blok z napisem zatrzymaj ten skrypt. Do niego dodano element, który zawiera równanie: jeżeli zmienna liczba jest mniejsza od elementu środek z listy odcinków, to uruchom ten skrypt od nowa z nowymi parametrami: liczba, zero, środek minus jeden. W przeciwnym razie uruchom ten skrypt od nowa z nowymi parametrami: liczba, środek plus jeden, koniec listy. Jeżeli ta funkcja nie jest spełniona, to występuje komunikat Niestety, ale podana liczba nie znajduje się na liście. Na dole jest blok z napisem zatrzymaj ten skrypt, który kończy skrypt. — Przykładowa definicja bloku dziel_zwyciezaj
Źródło: GroMar Sp. z o.o., licencja: CC BY-SA 3.0.

R1Qx2eNA8lI9g

Ćwiczenie 2

Źródło: GroMar Sp. z o.o., licencja: CC BY-SA 3.0.

R1Pv6AbGDCiZh

Ćwiczenie 3

Źródło: GroMar Sp. z o.o., licencja: CC BY-SA 3.0.

Wykorzystaj poniższe pole na zapisanie swoich notatek i przemyśleń.

RjqkjgO9biQil

Dzienniczek, w którym możesz zapisać swoje notatki i przemyślenia.

Źródło: GroMar, licencja: CC BY 3.0.

Czy można zbudować trójkąt - gra matematyczna

Operacje na listach w Scratch: tworzenie i sortowanie listy, minimum i maksimum

Sortowanie elementów listy