How many times are we copying elements to the right while applying insertion sort on the...

How many times are we copying elements to the right while applying insertion sort on the input sequence 3 5 2 8 3?

How many times are we copying elements to the right while applying insertion sort on the input sequence 5 4 3 2 1?

Expert Solution

1.3,5,2,8,3:

Intially the array is empty. So no copy operation. 3 is inserted into an array. While inserting 5 it won't occur any problem due to 3<5. While inserting 2 , 5 has to be copied to right by one position and 3 by one position. So till now 2 copy operations are done. Now, while inserting 8 no copy operations. While inserting we need to perform 3 copy right operations,for making place for 3.so, totally 5 copy operations are required during insertion sort for the sequence.

5, 4,3,2,1.

While inserting 5 no need to perform any copy operation. While inserting 4 we need to perform one copy right operation. For inserting 3 we need to perform 2 copy right operations. So totally 3 copy right operations are needed upto this iteration. For inserting 2 we do require 3 copy operations. So 6 copy right operations. For inserting 1 we do require 4 copy right operations. So finally, we do require 10 copy right operations while applying insertion sort.

If you have any queries... Please comment.. Thank you

venereology answered 2 hours ago

For this assignment, find out how to do a bubble sort, selection sort, or insertion sort...

For this assignment, find out how to do a bubble sort, selection sort, or insertion sort in Java. You have the option to choose but you must label (with comments) the algorithm you choose to implement. Convert that algorithm to a generic algorithm and constraint it to only using numerics. Your method should accept an array as a parameter and sort the content of the array. If you wish, you can throw an exception if the contents of the array...

Hello, as we know the invariant for the insertion sort is Invariant: at the start of...

Hello, as we know the invariant for the insertion sort is Invariant: at the start of each for loop, A[1…j-1] consists of elements originally in A[1…j-1] but in sorted order Please proof this invariant by mathematical induction method.

Exercise 4–Timing Sorting AlgorithmCollect the run times for either selection sort or insertion sort (use random...

Exercise 4–Timing Sorting AlgorithmCollect the run times for either selection sort or insertion sort (use random values for an array and sorted values; sorted the same list twice and collect time each time) for the following array sizes: 1000, 2000, and 10000. You should be able to confirm that the runtime is n^2 for unsorted list (i.e., going from 1000 to 2000 should be about 4 times slower and going from 1000 to 10000 should be about 100times slower). Question...

How many times will the following while loop iterate? int i = 1; while (i <...

How many times will the following while loop iterate? int i = 1; while (i < 5) { i = i + 1; System.out.println(“Hello!”); } Group of answer choices 4 0 5 It will iterate infinitely

Fair Dice We roll a fair dice 10 times and register how many times we obtained...

Fair Dice We roll a fair dice 10 times and register how many times we obtained 5. (a) Find the probability to obtain 5 seven times. (b) Estimate the number of fives that will come out with the probability 0.35. (c) What is the probability of geting 30 fives when rolling a fair dice 45 times? (d) How many fives will come out with a probability of 0.25, when rollong a fair dice 45 times?

Please show all work and explain Very confused We can express insertion sort as a recursive...

**Please show all work and explain** Very confused We can express insertion sort as a recursive procedure as follows. In order to sort A[1..n], we recursively sort A[1..n-1] and then insert A[n] into the sorted array A[1..n-1]. Write a recurrence for the running time of this recursive version of insertion sort.

How many elements of order 2 are there in S5 and in S6? How many elements...

How many elements of order 2 are there in S5 and in S6? How many elements of order 2 are there in Sn? (abstract algebra)

C++ Visual Studios How many times will "!" print? int i = -5 while(-5 <= i...

C++ Visual Studios How many times will "!" print? int i = -5 while(-5 <= i <= 0) { cout << "!"; --i; }

1. Commute times in the U.S. are heavily skewed to the right. We select a random...

1. Commute times in the U.S. are heavily skewed to the right. We select a random sample of 240 people from the 2000 U.S. Census who reported a non-zero commute time. In this sample the mean commute time is 28.9 minutes with a standard deviation of 19.0 minutes. Can we conclude from this data that the mean commute time in the U.S. is less than half an hour? Conduct a hypothesis test at the 5% level of significance. What is...

Commute times in the U.S. are heavily skewed to the right. We select a random sample...

Commute times in the U.S. are heavily skewed to the right. We select a random sample of 230 people from the 2000 U.S. Census who reported a non-zero commute time. In this sample the mean commute time is 28.6 minutes with a standard deviation of 19.3 minutes. Can we conclude from this data that the mean commute time in the U.S. is less than half an hour? Conduct a hypothesis test at the 5% level of significance. What is the...

Question