1) Consider the array based list of (10, 4, 8, 2, 7) as input for selection sort
ID: 3627908 • Letter: 1
Question
1) Consider the array based list of (10, 4, 8, 2, 7) as input for selection sort and insertion sort algorithms in the following:The number of comparisons made by the selection sort is
The number of comparisons made by the insertion sort is
Note that each swap requires 3 moves. The number of moves made by the selection sort is
The number of moves made by the insertion sort is
2) Consider the array based list of (5, 4, 3, 2, 1) as input for selection sort and insertion sort algorithms in the following:
The number of comparisons made by the selection sort is
The number of comparisons made by the insertion sort is
Note that each swap requires 3 moves. The number of moves made by the selection sort is
The number of moves made by the insertion sort is
3) Consider the array based list of (1, 2, 3, 4, 5) as input for selection sort and insertion sort algorithms in the following:
The number of comparisons made by the selection sort is
The number of comparisons made by the insertion sort is
Note that each swap requires 3 moves. The number of moves made by the selection sort is
The number of moves made by the insertion sort is
Explanation / Answer
Selection sort finds the minimum value and swaps it to the each consecutive position in the list. http://en.wikipedia.org/wiki/Selection_sort Insertion sort inserts each consecutive element into the correct position in a list that begins empty and is maintained to be sorted. http://en.wikipedia.org/wiki/Insertion_sort 1) Consider the array based list of (10, 4, 8, 2, 7) as input for selection sort and insertion sort algorithms in the following: The number of comparisons made by the selection sort is 5+4+3+2+0 = 14 1. 5 comparisons to find minimum 2. 4 comparisons to find minimum of remaining list 3. 3 comparisons to find minimum of remaining list 4. 2 comparisons for the next two numbers 5. 0 comparison for the final number The number of comparisons made by the insertion sort is 7 List is built as follows: 1. 10 2. 4, 10 (1 comparison) (1 move) 3. 4, 8, 10 (2 comparisons) (1 move) 4. 2, 4, 8, 10 (1 comparison) (3 moves) 5. 2, 4, 7, 8, 10 (3 comparisons) (2 moves) Note that each swap requires 3 moves. The number of moves made by the selection sort is 4*3 = 12 1. Minimum is 2, swap with 10 2. Minimum is 4, don’t swap 3. Minimum is 7, swap with 8 4. Minimum is 8, swap with 10 The number of moves made by the insertion sort is 7 moves. 2) Consider the array based list of (5, 4, 3, 2, 1) as input for selection sort and insertion sort algorithms in the following: The number of comparisons made by the selection sort is 14 (see above). The number of comparisons made by the insertion sort is 5 (1 comparison each) 1. 5 2. 4, 5 (1 move) 3. 3, 4, 5 (2 moves) 4. 2,3,4,5 (3 moves) 5. 1,2,3,4,5 (4 moves) Note that each swap requires 3 moves. The number of moves made by the selection sort is 3*2=6. 1. Swap 1 and 5 2. Swap 2 and 4 The number of moves made by the insertion sort is 10 moves. 3) Consider the array based list of (1, 2, 3, 4, 5) as input for selection sort and insertion sort algorithms in the following: The number of comparisons made by the selection sort is 14 (see above). The number of comparisons made by the insertion sort is 10 1. 1 2. 1, 2 (1 move) (1 comparison) 3. 1, 2, 3 (2 moves) (2 comparisons) 4. 1, 2, 3, 4 (3 moves) (3 comparisons) 5. 1, 2, 3, 4, 5 (4 moves) (4 comparisons) Note that each swap requires 3 moves. The number of moves made by the selection sort is 0. The number of moves made by the insertion sort is 10.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.