Question: Let A(i : j) denote the array of items in positions i through j of the Array A. In selection sort, we use the method of Exercise to find the largest element of the array A and its position k in the array, then we exchange the elements in position k and n of Array A, and we apply the same procedure recursively to the array A(1 : n - 1). (Actually we do this if n > 1; if n = 1 we do nothing.) What is the expected total number of times we assign a value to L in the algorithm selection sort?
Exercise: Given an array A of length n (chosen from some set that has an underlying ordering), we can select the largest element of the array by starting out setting L = A(1), and then comparing L to the remaining elements of the array one at a time, replacing L by A(i) if A(i) is larger than L. Assume that the elements of A are randomly chosen. For i > 1, let Xi be1if element i of A is larger than any element of A(1 : i - 1). Let X1 = 1. Then what does X1 + X2 + ··· + Xn have to do with the number of times we assign a value to L? What is the expected number of times we assign a value to L?