[20, 62, 71, 85, 86, 61] Give me the number of comparisons and swaps for the above list, following insertion sort algorithm.
Question
Give me the number of comparisons and swaps for the above list, following insertion sort algorithm.
List: [20, 62, 71, 85, 86, 61]
Solution
Sure, let's go through the insertion sort algorithm step by step for the given list [20, 62, 71, 85, 86, 61].
-
The list starts with [20, 62, 71, 85, 86, 61]. The first element, 20, is already sorted. So, no comparisons or swaps are needed here.
-
Next, consider the second element, 62. It's already in the correct position relative to 20. So, 1 comparison is made, but no swaps.
-
The third element is 71. It's also in the correct position relative to 20 and 62. So, 2 comparisons are made, but no swaps.
-
The fourth element is 85. It's in the correct position relative to 20, 62, and 71. So, 3 comparisons are made, but no swaps.
-
The fifth element is 86. It's in the correct position relative to 20, 62, 71, and 85. So, 4 comparisons are made, but no swaps.
-
The last element is 61. It's not in the correct position. It needs to be placed between 20 and 62. So, 5 comparisons are made, and 4 swaps are needed to put 61 in its correct position.
So, in total, there are 1 + 2 + 3 + 4 + 5 = 15 comparisons and 4 swaps.
Similar Questions
Given list [16, 32, 35, 99, 37, 42, 67, 88, 68], how many swaps are needed to sort the list?
Given an array of 6 numbers [6,8,19,48,9,90]and applying insertion sort, how many swaps must occur before the array is sorted?1 point42 6
What will be the number of passes to sort the elements using insertion sort?14, 12,16, 6, 3, 106571
A sort which compares adjacent elements in a list and switches where necessary is
Given list [22, 29, 37, 38, 27, 35, 36, 39, 31, 26], when i is 4, how many swaps will be performed in the inner loop?
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.