Lekcja_04 - sortowanie1. Sortowanie2. SortowanieWyjścieSortowanie1.(1p) Jaki jest stan tablicy 3, 5, 2, 4, 1 po wykonaniu dwóch iteracji algorytmu sortowania przez wybór (SelectionSort)?1,2,5,4,3 1,2,3,4,51,2,3,5,41,5,2,4,31,2,5,3,42. (1p) Dla którego z wymienionych ciągów algorytm InsertionSort (sortujący w porządku niemalejącym) wykona najmniej porównań ?Dla ciągu uporządkowanego rosnąco, Dla ciągu uporządkowanego malejąco,Dla losowo wybranego ciągu, który nie jest ani ściśle malejący ani ściśle rosnący.3. (1p) Czy koszt sortowania algorytmem SelectionSort zależy od ustawienia elementów w ciągu?zależynie zależy4. (1p) Jaki będzie stan ciągu 4, 5, 1, 2, 3, po wykonaniu dwóch iteracji w algorytmie sortowania InsertionSort?1, 2, 4, 5, 3 1, 2, 3, 4, 51, 4, 5, 2, 31, 2, 5, 3, 41, 2, 5, 4, 35. (1p) Dla którego ciągu algorytm QuickSort wykona mniej porównań: dla uporządkowango rosnąco, czy dla uporządkowanego malejąco?dla uporządkowanego rosnącodla uporządkowanego malejącow obu przypadkach wykona tyle samo porównań6. (1p) Który algorytm wykona najmniej porównań dla ciągu już uporządkowanego?SelectionSortInsertionSort MergeSortQuickSort7. (1p) Ile porównań wykona algorytm SelectionSort w trakcie sortowania tablicy A?7, gdy A jest uporządkowaną tablicą siedmioelementową15, gdy A = {2,4,5,3,6,9,1}36, gdy A = {1,2,3,4,5,6}45, gdy A jest dowolną tablicą o 10 elementach8. (1p) Koszt scalenia dwóch uporządkowanych ciągów jest proporcjinalny do sumy, czy do iloczynu długości tych ciągów?do iloczynu długości ciągówdo sumy długości ciągówzależy jeszcze od innych parametrów9. (1p) Jaki jest koszt algorytmu sortowania przez scalanie MergeSort zastosowanego do k-elementowego ciągu?Theta(n2)O(n)Theta(k lg k)Theta(n lg n)10. (1p) Jaka jest wysokość drzewa rekurencyjnych wywołań algorytmu MergeSort zastosowanego do ciągu o 512 elementach?5678911. (2p) Niech e[1],...,e[2n] będzie ciągiem parami różnych elementów. Jaki jest koszt sortowania tego ciągu, jeśli zastosowano następujący algorytm sortowania Sort? Sort: w kolejnych n krokach algorytmu wybieramy, optymalnym algorytmem min_max, minimum i maksimum, i zamieniamy te elementy odpowiednio z elementami na pozycji i-tej i pozycji n-i+1-szej, gdzie i zmienia się od 1 do n. O(2n)O(2n lg( 2n)))O(n^2)12. (1p) Jaka jest co najmniej długość ścieżki od korzenia do liścia w najgorszym przypadku w drzewie decyzyjnym dowolnego algorytmu sortującego przez porównywania ciąg n elementowy?Theta(n lg n)Theta(lg n) Theta(n)Odpowiedzi :  Wyniki