Porządkowanie przez zliczanie

Temat: Porządkowanie przez zliczanie

  • sortowanie przez zliczanie,
  • realizowanie algorytmu sortowania przez zliczanie w Scratchu,
  • tworzenie klonu duszków.

Sortowanie to porządkowanie zbioru elementów względem konkretnych cech każdego elementu, np. malejąco albo alfabetycznie. Nie ma idealnego algorytmu sortującego – dobór algorytmu zależy od sytuacji. Podczas tej lekcji poznasz sortowanie oparte na zliczaniu.

ZASADY SORTOWANIA

Działanie algorytmu sortowania przez zliczanie najlepiej przedstawić za pomocą przykładu. Jak uporządkować rosnąco ciąg liczb 4, 3, 4, 1, 4, 4, 2, 1, 4 i 3?

Dla każdej możliwej wartości liczbowej (1, 2, 3 lub 4) należy ustalić licznik do zliczania każdej z tych wartości i ustalić jego wartość początkową na 0. Potem trzeba przejrzeć kolejne elementy listy i zliczyć ich wystąpienia. Na koniec pozostaje zsumować wartość licznika oraz licznika poprzedniej liczby, aby ustalić pozycję ostatniego elementu każdej wartości liczbowej i odpowiednio ustawić kolejne elementy listy.

 

Porządkowanie przez zliczanie polega na przeglądaniu kolejnych elementów zbioru, zliczaniu ich wystąpień oraz zapisywaniu na przygotowanej do tego celu liście i – ostatecznie – zapisaniu liczb według określonego porządku.

 

Wybierz z biblioteki duszka przedstawiającego liczbę 1 (Glow-1), a następnie na karcie Kostiumy dodaj trzy kostiumy w postaci liczb 2, 3 i 4. Nazwij kostiumy kolejno 1, 2, 3 i 4.

Duszek będzie ukryty, jego postać posłuży do utworzenia 11 klonów, tj. identycznych kopii, które mają wszystkie cechy i funkcjonalności swojego wzorca. Każdy z klonów będzie miał losowo wybrany kostium.

Tworzymy 2 zmienne:

  • x – przechowującą odległość między kolejnymi klonami (40), kolejne duszki muszą być przesunięte, aby były widoczne.
  • los – przechowującą numer kostiumu powstałego klonu (wylosowaną liczbę od 1 do 4); 

  • Przetestuj działanie obu skryptów kilka razy – sprawdź, czy tworzenie klonów przebiega poprawnie.
  • Aby zliczyć, ile razy występuje każda liczba, musisz utworzyć cztery zmienne, np. a, b, cd. W osobnym skrypcie zielonej flagi ustaw początkowe wartości tych zmiennych na 0.

Zdefiniuj blok zliczaj, który będzie zliczał wystąpienia poszczególnych liczb – 1, 2, 3 i 4.

Uzupełnij powyższy skrypt o zliczanie kolejnych liczb – 2, 3 i 4.

  • Przetestuj kilkakrotnie działanie skryptów.
  • Uzupełnij skrypt zielonej flagi z początkowymi wartościami zmiennych. Utwórz zmienną posortowana i wstaw ją do bloku ustaw (…) na (…) z domyślą wartością 0. Wyczyść pole edycji bloku. Będziesz tam dostawiać kolejno tyle jedynek, ile wynosi wartość zmiennej a, tyle dwójek, ile wynosi wartość zmiennej b itd.

Skip to content