ASD ep 02 2005 4

Algorytmy i Struktury Danych

Egzamin poprawkowy 16 lutego 2005

Imię i nazwisko......................................................Nr indeksu.........................

Zadanie 4 Danyjest ciąg złożony z zer i jedynek.

Polecenia:

(a)    Zaproponuj algorytm, o możliwie małym koszcie, do posortowania tego ciągu w porządku niemalejącym. Jaki jest koszt zaproponowanego algorytmu?

(b)    Zastosuj do posortowania tego samego ciągu algorytm QuickSort i oszacuj poniesiony koszt. Uzasadnij swoją odpowiedź.

(c)    Załóżmy, że dysponujemy wyrocznią, która dla dowolnego ciągu potrafi stwierdzić, czy jest on już uporządkowany, czy nie. Użyj wyroczni do takiego zmodyfikowania algorytm QuickSort, by nie wykonywał on niepotrzebnych porównań, gdy rozważany ciąg już jest posortowany. Zapisz uzyskany algorytm w pseudokodzie zakładając, że masz daną,procedurę Split oraz funkcję Wyrocznia, gdzie Wyrocznia(c) = true wttw c jest cięgiem uporządkowanym niemalejąco.