The selection sort begins by finding the least element in the list. This element is moved to the front. Then the least element among the remaining elements is found and put into the second position....

The selection sort begins by finding the least element in the list. This element is moved to the front. Then the least element among the remaining elements is found and put into the second position. This procedure is repeated until the entire list has been sorted.

41. Sort these lists using the selection sort.

a) 3, 5, 4, 1, 2

b) 5, 4, 3, 2, 1

c) 1, 2, 3, 4, 5

1. Write the selection sort algorithm in pseudo code.

2. Describe an algorithm based on the linear search for determining the correct position in which to insert a new element in an already sorted list.

3. Describe an algorithm based on the binary search for determining the correct position in which to insert a new element in an already sorted list.

4. How many comparisons does the insertion sort use to sort the list 1,
2, . . . , n?

5. How many comparisons does the insertion sort use to sort the list
n, n
− 1, . . . ,
2,
1?