Sort the below numbers using selection sort show the steps 1

Sort the below numbers using selection sort: (show the steps) 1, 4, 2, 5, 6, -2, 10 Find the pivot using median of three, and then apply the partitioning algorithm to find a_left and a_right. 1, 5, 14, 8, 36, 25, 21, 19, 12 What is the running time of Insertion Sort if all elements are equal? Explain.

Solution

7.In selection sort algorithm, we search for the lowest element and arrange it to the proper location. We swap the current element with the next lowest number.

steps:

1,4,2,5,6,-2,10

-2,4,2,5,6,1,10

-2,1,2,5,6,4,10

-2,1,2,4,6,5,10

-2,1,2,4,5,6,10

8,ans

1,5,14,8,36,25,21,19,12

left=1

right=12

center(left+right)/2=1+12=13/2=6.5

pivot=median of s[left]s[right]s[center]

=1,12,6.5

=12

9.Let A denote the array being sorted. For each element A[i], you check the preceding element A[i-1] and find they are equal. And you do not check further. Thus, you perform exactly n-1 comparisons, which makes the algorithm run in O(n) time.