Studia Licencjackie / Inżynierskie

Algorytmy i struktury danych

Lista zadań nr 2

1.

Ustal dla jakich danych algorytmy sortowania przez selekcję i przez wstawianie
wykonają:

a)

najmniej

b)

najwięcej

zamian i porównań elementów sortowanej tablicy (chodzi o porównania/zamiany
elementów sortowanej tablicy lub zmiennych tego samego typu co sortowane elementy).
Podaj liczbę wykonywanych porównań i zamian w zależności od długości sortowanego
ciągu danych.
Uwaga: osobno podaj wynik dla zamian i dla porównań.
Wskazówka: rozważ dane wejściowe tworzące ciąg rosnący, ciąg malejący, ciąg losowy.

2.

Zapoznaj się z algorytmem sortowania bąbelkowego i przedstaw go. Uzasadnij
poprawność tego algorytmu.

3.

Ustal dla jakich danych algorytm sortowania bąbelkowego wykona:

a)

najmniej

b)

najwięcej

zamian i porównań elementów sortowanej tablicy (chodzi o porównania/zamiany
elementów sortowanej tablicy lub zmiennych tego samego typu co sortowane elementy).
Podaj liczbę wykonywanych porównań i zamian w zależności od długości sortowanego
ciągu danych.

4.

Podaj algorytm, który znajduje w tablicy a[0],...,a[n-1] najczęściej występujący element.
Postaraj się, aby czas działania Twojego rozwiązania był jak najmniejszy. Algorytm
w pełni rozwiązujący to zadanie powinien działać w czasie O(n

⋅

k), gdzie k to liczba

różnych elementów występujących w tablicy.
Przykład
W tablicy a=[5, 7, 13, 7, 5, 5, 7] wartość k wynosi 3, ponieważ występują w niej trzy
różne elementy: 5, 7, 13.

5.

Napisz funkcję, która dla danej tablicy a, liczby n i wartości x sprawdza, czy x występuje
wśród elementów a[1], a[2], …,a[n]. W celu przyspieszenia wyszukiwania wykorzystaj
a[0] jako wartownika.

6.

Podaj ile co najwyżej porównań wymaga wyszukiwanie binarne (w wersji z wykładu),
gdy rozmiar przeszukiwanych danych, n, wynosi odpowiednio: 10, 10

2

, 10

3

, 10

6

, 10

9

.