Run the iterative version of the selection sort algorithm on

Run the iterative version of the selection sort algorithm on an array containing the following elements: 34 72 81 19 27 36 50 Use brackets to indicate the portion of the array currently being sorted, as in the first half of Figure 3.3. Run the iterative version of insertion sort on an array containing the following elements: 34 72 81 19 27 36 50 Use brackets to indicate the portion of the array that\'s already sorted, as in the second half of Figure 3.8. Run merge sort on an array containing the following elements: 34 72 81 19 27 36 50 42 Show the entire recursion, as in Figure 3.13 of the notes. Consider the recurrence relation T(n) = T([n/2]) + T([n/2]) + bn^2, if n greaterthanorequalto 2 T(1) = Theta(1) Assuming that n is a power of 2, use a recursion tree to solve this recurrence. Use induction to prove that the upper bound you obtained in the previous exercise holds in the general case, when n is not necessarily a power of 2. (Do only the upper bound.)

Solution

Run the iterative version of the selection sort algorithm on an array containing elements:
34   72   81   19   27   36   50

The algorithm for selection sort in simple terms is:
For i = 1 : n-1
   Select the largest of first n-i+1 elements.
   Exchange the largest element with (n-i+1)th element.
Here n value is: 7.
So, the sorting goes like this:

i = 1: Select the largest of first 7 elements. i.e., 81. Exchange with 7th element.
[34   72   50   19   27   36   81]

i = 2: Select the largest of first 6 elements. i.e., 72. Exchange with 6th element.
[34   36   50   19   27   72]   81

i = 3: Select the largest of first 5 elements. i.e., 50. Exchange with 5th element.
[34   36   27   19   50]   72   81

i = 4: Select the largest of first 4 elements. i.e., 36. Exchange with 4th element.
[34   19   27   36]   50   72   81

i = 5: Select the largest of first 3 elements. i.e., 34. Exchange with 3rd element.
[27   19   34]   36   50   72   81

i = 6: Select the largest of first 2 elements. i.e., 27. Exchange with 2nd element.
[19   27]   34   36   50   72   81

Exit the loop. So, now the sorted list is:
19   27   34   36   50   72   81