Proponuję porozmawiać o wybranym algorytmie sortowania np. mege_sort albo insertion sort (inne studenci będą robili samodzielnie).
Studenci mogliby bez zaglądania do notatek zaimplementować ten algorytm w wersji z wykładu i w wersji nieco zmodyfikowanej:
Np. dla merge_sort , niech długość ciągu będzie dowolną liczbą naturalną
Np. dla insertion_sort, niech wstawianie elementu na właściwą pozycję odbywa się w dwóch etapach:1. metodą binarnych poszukiwań znajdujemy właściwą pozycję elementu 2. przesuwamy w prawo o 1 miejsce wszystkie elementy poprzedzające tę pozycję.
Przedyskutować, jak zmieni się (ewentualnie) koszt algorytmu.
Nie wiem, czy Państwo już robiliście wejściówkę z badania poprawności algorytmów, specyfikacji itd.. Ja jeszcze nie i mam zamiar zrobić ją dziś.
Wejściówka 3 Poprawność algorytmu
Podany algorytm działa w strukturze liczb naturalnych.
(a) Zbadać, jaka jest zależność między zmiennymi po
wykonaniu algorytmu
(b) Podać niezmiennik pętli.
(A1)
Begin
s := x; i := 1;
While i < y do
s := s + 1;
i := i + 1;
Od
End;
(A2)
Begin
S := 0; i := 0; p:=1;
While i < n do
s := s + p; p := p*2;
i := i + 1;
Od
End;
(A3)
Begin
s := 0; i := 0;
While i < n do
s := s + (2*i+1);
i := i + 1;
Od
End;