Zadanie 4: Rozważmy algorytm sortowania QuickSortSplit postaci: void QuickSortSplit(int…
- User
Zadanie 4: Rozważmy algorytm sortowania QuickSortSplit postaci: void QuickSortSplit(int E[]) { // E - niepusta tablica parami różnych liczb naturalnych
int m = 0, n = size(E); m = Split(E); // algorytm składowy Split if (m > 1) QuickSortSplit(E[0..m-1]); // wywołanie rekurencyjne alg. // dla lewego fragmentu podtablicy if ((n - m - 1) > 1) QuickSortSplit(E[m + 1..n - 1]); // wywołanie rekurencyjne // alg. dla prawego fragmentu podtablicy}
dla danych wejściowych: • tablica elementów: E =[ 9,6,1,17,18,10,11,15, 2,14, 16] , Które z poniższych zdań jest prawdziwe? a) W rozważanym przypadku liczba wykonań rekurencyjnych algorytmu QuickSortSplit (tj. bez głównego wywołania algorytmu) jest równa dokładnie liczbie wywołań rekurencyjnych rozważanego algorytmu dla danych wejściowych [9, 15, 11, 1, 14, 10, 17, 2, 16, 18, 6] b) W rozważanym przypadku wysokość drzewa wywołań rekurencyjnych algorytmu QuickSortSplit jest równa dokładnie wysokości drzewa wywołań rekurencyjnych rozważanego algorytmu dla danych wejściowych [17, 15, 16, 18, 9, 10, 6, 11,2,1,14] c) W rozważanym przypadku liczba wykonań algorytmu Split jest równa dokładnie liczbie wykonań rozważanego algorytmu dla danych wejściowych [16, 14, 17, 10, 18, 2, 6, 9, 11, 15, 1]
- Assistant
Option (b) is true.
In this problem, we need to evaluate statements about a QuickSort algorithm's behavior on different input arrays and determine which statement is true.
Upon analyzing the algorithm and simulating its execution on the given arrays, we need to compare the height of the recursion call trees for two specific input arrays.
For the original array ( E = [9,6,1,17,18,10,11,15,2,14,16] ), we determine the recursion depth by following the recursive calls. We find that the maximum recursion depth is 5.
Next, we analyze the array given in option (b): ( E'' = [17,15,16,18,9,10,6,11,2,1,14] ). We perform the same steps and again find that the maximum recursion depth is 5.
Since the heights of the recursion call trees for both arrays are the same (both have a maximum depth of 5), statement (b) is the true statement.
Answer: b)