1. Klasówka 2019/20 (15.11.2019)#
Zadanie 1 [5 punktów]#
[2 punkty] Ile jest permutacji liczb od 1 do n o co najwyżej 2 inwersjach?
[3 punkty] Zaproponuj optymalny algorytm sortujący przez porównania ciągi różnowartościowe o co najwyżej 2 inwersjach.
Podpowiedź
Punkt b) możliwe ciągi:
ciąg posortowany (0 inwersji),
ciąg z zamienionymi sąsiednimi elementami ba (1 inwersja (b,a)),
ciąg z wzorcem cab (2 inwersje (c,a) i (c,b)),
ciąg z zamienionymi sąsiednimi elementami w różnych miejscach ba...dc (2 inwersje (b,a) i (d,c)).
Zadanie 2 [5 punktów]#
Rozważamy klasyczne sortowanie przez wstawianie tablicy \(a[1,\ldots,n]\) w porządku niemalejącym, w której zapisano pewną permutację liczb od 1 do n. Zaprojektuj wydajny algorytm, który dla danej zawartości tablicy a wyznaczy najmniejsze takie i, że podczas sortowania przez wstawianie a[i] jest porównywane najczęściej.
Zadanie 3 [10 punktów]#
Dana jest tablica \(a[1,\ldots,4n]\), w której znajduje się po n liczb ze zbioru {0,1,2,3}.
[5 punktów] Zaprojektuj liniowy algorytm sortujący tablicę a w miejscu.
[5 punktów] Podaj algorytm działający w czasie \(O(n \log n)\), który sortuje tablicę a w miejscu i stabilnie (tzn. kolejność elementów o tej samej wartości przed i po sortowaniu jest taka sama).
Podpowiedź
Punkt a) 3 krotne zastosowanie algorytm do problemu flagi polskiej (przebieg 1: B={0} C={1,2,3}, przebieg 2: B={0,1} C={2,3}, przebieg 3: B={0,1,2} C={3}).
Punkt b) 3 krotne zastosowanie algorytmu stabilnego sortowania ciągów 0/1 o złożoności \(O(n\log n)\).