Question textRecall the Naive 3-way partitioning algorithm. We provide it below, as given in the course notes. [table] 1 2 3 4 5 6 7 8 9 10 | function PARTITION(array[lo..hi], pivot) left = empty array // Store elements less than the pivot pivots = empty array // Store elements equal to the pivot right = empty array // Store elements greater than the pivot for i = lo to hi do if array[i] < pivot then left.append(array[i]) else if array[i] = pivot then pivots.append(array[i]) else right.append(array[i]) array[lo..hi] = left + pivots + right // Concatenate the arrays return lo + length(left) + ⌊length(pivots)/2⌋ // Return the position of the middle pivot [/table] Additionally, recall the quickselect algorithm. We provide it below, as given in the course notes. [table] 1 2 3 4 5 6 7 8 9 10 11 12 13 | function QUICKSELECT(array[lo..hi], k) if hi > lo then pivot = array[lo] // Choose the first element in the search range as the pivot mid = PARTITION(array[lo..hi], pivot) print(array) // Added for demonstration if k < mid then return QUICKSELECT(array[lo..mid - 1], k) else if k > mid then return QUICKSELECT(array[mid + 1..hi], k) else return array[k] else return array[k] [/table] Suppose we are executing quickselect using the naive paritioning algorithm above. You may assume that all arrays are 1-indexed.Given the input array [table] 87 | 39 | 56 | 68 | 27 | 41 | 78 | 19 [/table] Suppose we called QUICKSELECT(array[1..8], 6). Give the contents of the array for each print on line 5 until the algorithm terminates. No justification is required. Each horizontal row in the table below should correspond to a single print on line 5. There should be exactly 4 lines printed throughout execution. It is recommended that you do the busywork of this algorithm on paper, so that you can track the contents of each temporary array throughout execution. (For instance left = [a,b,c], pivot = d, right = [e,f,g]) [table] Index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 Print 1: | Answer 1 Question 4 | Answer 2 Question 4 | Answer 3 Question 4 | Answer 4 Question 4 | Answer 5 Question 4 | Answer 6 Question 4 | Answer 7 Question 4 | Answer 8 Question 4 Print 2: | Answer 9 Question 4 | Answer 10 Question 4 | Answer 11 Question 4 | Answer 12 Question 4 | Answer 13 Question 4 | Answer 14 Question 4 | Answer 15 Question 4 | Answer 16 Question 4 Print 3: | Answer 17 Question 4 | Answer 18 Question 4 | Answer 19 Question 4 | Answer 20 Question 4 | Answer 21 Question 4 | Answer 22 Question 4 | Answer 23 Question 4 | Answer 24 Question 4 Print 4: | Answer 25 Question 4 | Answer 26 Question 4 | Answer 27 Question 4 | Answer 28 Question 4 | Answer 29 Question 4 | Answer 30 Question 4 | Answer 31 Question 4 | Answer 32 Question 4 [/table] Please answer all parts of the question.Check Question 4多项填空题