Cele lekcji:

• Uświadomisz sobie jak ważne jest porządkowanie danych.

• Lepiej zrozumiesz algorytmy wyszukiwania (liniowego i binarnego).

• Poznasz algorytmy sortowania bąbelkowego i przez wstawianie.

• Dowiesz się jak w języku Python używać list w argumentach funkcji.

Ćwiczenie 1

Z jakimi uporządkowanymi zbiorami danych masz do czynienia na co dzień, Wymień co naj mniej pięć konkretnych przykładów.

Ćwiczenie 2

• Według jakiego kryterium uporządkowano zawodniczki w tabeli 8.1 (patrz jamboard L8)

• Czy klasyfikacje dla każdej pojedynczej konkurencji są tworzone na podstawie wyników uporządkowanych malejąco?

Ćwiczenie 3

Ile sprawdzeń (porównań 2 liczb) wystarczy by rozstrzygnąć, czy w ciągu komórek z rysunku 8.6 (patrz jamboard L8) znajduje się liczba 80? Zapisz indeksy oraz wartości komórek, które kolejno będą sprawdzane.

Zagadnienia:

• Sortowanie przez wstawianie (ang. insertion sort) sortowanie przez wstawianie w tańcu

• Zmienna pomocnicza.

• Pętla while wewnątrz pętli for.

Algorytm sortowania przez wstawianie jest szczególnie efektywny przy sortowaniu zbiorów prawie uporządkowanych, np rankingów aktualizowanych na bieżąco podczas zawodów sportowych.

Ćwiczenie 8a [144] 

Napisz kod źródłowy funkcji Wstawianie i napisz program, w którym tę funkcję zastosujesz, Sprawdź działanie programu (zapisz pod nazwą L10a.py)

Podsumowanie:

• Sortowanie danych to ustawianie ich w zadanej kolejności według określonego kryterium.

• Uporządkowanie informacji ma ogromne znaczenie w wielu aspektach życia — zarówno w technologii komputerowej, jak i dziedzinach zupełnie z nią niezwiązanych.

• Sortowanie bąbelkowe polega na cyklicznym porównywaniu par elementów sąsiednich (zaczynając od pierwszej pary na liście) i zamianie miejscami tych elementów, które nie są w odpowiedniej kolejności.

• Sortowanie przez wstawianie polega na przenoszeniu jeden po drugim kolejnych elementów z nieuporządkowanego fragmentu listy w odpowiednie miejsce fragmentu już uporządkowanego.

• Aby funkcji zdefiniowanej w języku Python przez użytkownika umożliwić dostęp do listy zdefiniowanej w części głównej programu (np. o nazwie 1Lista), w nagłówku funkcji jako parametr trzeba podać dowolną nazwę, która będzie w kodzie funkcji używana jako nazwa listy, np. def Funkcja(lista).

• Funkcję wywołuje się, podając jako parametr aktualny nazwę listy, np. Funkcja(1istaA). Wszystkie operacje są wykonywane przez funkcję bezpośrednio na liście i zmiany są pamiętane po zakończeniu działania funkcji

Ćwiczenie 8b [144] 

Zmodyfikuj program Sortowanie przez wstawianie tak aby sortował 2 listy liczb całkowitych, np. o nazwach ListaA i ListaB. Następnie program ma posortować listę, która powstanie z połączenia dwóch list wcześniej posortowanych. (zapisz pod nazwą L11.py) L11.py v.1