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
.