6. Kolokwium - [2000]

2000-05-31, 12:00

Sprawdzian z Analizy Algorytmów Grupa B Zadanie 1 W przypadku sortowania dużych zbiorów danych, nie jest możliwe jednoczesne zapamiętanie wszystkich rekordów w pamięci. Ciąg rekordów do sortowania musi być przechowywany na dysku i sortowany tak, żeby w pamięci nic musiał znaleźć się naraz cały ciąg. Jedna z metod sortowania takich .danych jest następująca: dzielimy plik na dwa mniejsze (np. parzyste elementy kopiujemy do jednego, nieparzyste do drugiego). Otwieramy obydwa pliki do odczytu i tworzymy trzeci - z ciągiem uporządkowanych par elementów. Uzyskany tak plik znowu dzielimy na dwa; pierwszą parę przepisujemy do pierwszego, drugą do drugiego, trzecią znowu do pierwszego itd. Polem łączymy te dwa pliki tak, aby uzyskać jeden, będący ciągiem uporządkowanych czwórek. Nie wymaga to swobodnego dostępu do czytanych plików, odczyt jest zawsze sekwencyjny. W kolejnym kroku znowu dzielimy ten ciąg czwórek na dwa pliki, które łączymy w ciąg ósemek itd. Przedstawić przykład sortowania tą metodą ciągu kluczy: 5,4,9,2,7,3,6, 1 i wyznaczyć rząd złożoności algorytmu. Zadanie 2 W tablicach A1, A2[0..n-1] zapisane są dwa ciągi znaków (‘a’<=Ax[i]<=’z’). Dany jest następującalgorytm: function cmp:boolean; begin i:=0; while (A1[i]-A2[I]) and (i 0