Opis metody "sortowania przez wstawianie"
Zadanie 60
WE: tablica A[1..n]
WY: tablica A posortowana "<=" (niemalejąco) metodą "sortowania przez wstawianie".
Wymagania: Przeszukiwanie część posortowanej zaczynaj od prawej strony
czyli od wyższych indeksów.
Dodatkowo: Zakładamy że operacją dominującą jest porównywanie elementów
tablicy. Przez czas działania rozumiemy liczbę operacji dominujących. Oszacuj czas działania
w najgorszym przypadku dla następujących danych wejściowych:
1.dowolnego ciągu liczb;
2.posortowanego rosnąco ciągu (różnych) liczb;
3.posortowanego malejąco ciągu (różnych) liczb;
4.ciągu liczb składającego się z jednej i tej samej liczby.
Zadanie 60.1
Zapisz algorytm "sortowania przez wstawianie" nieco inaczej niż
w zadaniu 60: różnica polega na tym że przeszukiwanie posortowanej części zaczyna
się od lewej strony. Oszacuj czas działania tak jak w zadaniu 60 (rozważając
wszystkie 4 przypadki danych wejściowych).
Zadanie 60.2
Algorytm "sortowania przez wstawianie" z zadania 60 sortuje tablicę A[1..n]. Oszacuj
możliwie dokładnie czas działania algorytmu dla dowolnego ciągu liczb.
Operacja dominująca to porównanie elementów tablicy A.
Wskazówka: algorytm składa się z pętli; najpierw oszacuj możliwie
najdokładniej (z góry) czas działania pojedynczej iteracji, potem zsumuj te
wartości ...
Zadanie 61
WE: tablica A[1..n]
WY: tablica A posortowana ">=" (nierosnąco) metodą "sortowania przez wstawianie".
Zadanie 62
WE: tablica A[1..n]
WY: tablica A posortowana "<=" metodą "sortowania przez wstawianie".
Wymagania: Zaimplementuj algorytm w taki sposób aby część posortowana
powstawała po prawej stronie.
Opis metody "sortowania przez selekcje"
Zadanie 63
WE: tablica A[1..n]
WY: tablica A posortowana "<=" metodą "sortowania przez selekcje".
Wymagania: Użyj operacji minimum (w opisie algorytmu używa się maksimum
!).
Dodatkowo: Oszacuj czas działania tak jak w zadaniu 60.
Zadanie 64
WE: tablica A[1..n]
WY: tablica A posortowana "<=" metodą "sortowania bąbelkowego"
(chyba wszyscy znają tę metodę ?)
Dodatkowo: Oszacuj czas działania tak jak w zadaniu 60.
Zadanie domowe 70
Zapisz algorytm który oblicza C := A Ç
B, czyli przekrój zbiorów A i B.
Zbiory liczb są reprezentowane jako posortowane rosnąco tablice
w których liczby się nie powtarzają. Obowiązują oznaczenia jak w
zadaniu 52. Procedura musi działać w czasie O(n).
Wskazówka: przypomnij sobie algorytm scalania dwóch posortowanych ciągów
liczb ... .
Zadanie domowe 71
Zapisz algorytm który oblicza C := A \ B, czyli różnicę zbiorów A i B
(różnica ta zawiera elementy należące do A lecz nie należące do B).
Zbiory liczb są reprezentowane jako posortowane rosnąco tablice
w których liczby się nie powtarzają. Obowiązują oznaczenia jak w
zadaniu 52. Procedura musi działać w czasie O(n).
Zadanie domowe 72
Oszacuj czas działania "sortowania przez wstawianie" tak jak w zadaniu 60 (czyli rozpatrując 4 przypadki
danych wejściowych). Jednak tym razem za operację dominującą przyjmujemy
"przypisanie/odczytanie elementu tablicy A ORAZ porównywanie elementów tablicy
A".
Zadanie domowe 73
Oszacuj czas działania "sortowania przez selekcję", tak jak to
opisano w zadaniu 72.
Zadanie domowe 74
Oszacuj czas działania "sortowania bąbelkowego", tak jak to opisano w
zadaniu 72.