1. Klasówka 2019/20 (15.11.2019)

Zadanie 1 [5 punktów]

Słowa kluczowe: sortowanie, optymalne porównania

1. [2 punkty] Ile jest permutacji liczb od 1 do n o co najwyżej 2 inwersjach?

2. [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]

Słowa kluczowe: sortowanie

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.

Podpowiedź

TBD

Zadanie 3 [10 punktów]

Słowa kluczowe: sortowanie, w miejscu

Dana jest tablica \(a[1,\ldots,4n]\), w której znajduje się po n liczb ze zbioru {0,1,2,3}.

1. [5 punktów] Zaprojektuj liniowy algorytm sortujący tablicę a w miejscu.

2. [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)\).