Question

Date: December 12th, 2019 4. Describe why you selected the worstcase runtime above. Recall what we said about inversions and how the number of inversions is equivalent to the number of swaps for insertion sort. Also, recall the visualization from the notes on insertion First Name: Last Name: Hint: Given a list L = {4, 15, 104, Z. 11.2.14) where we are determining the number of inversions for 10, the inversions are underlined in red. I. INSERTION SORT 1. Given the figure below, considering that we are in the process of carrying out insertion sort on L and our position in the algorithm process is p=5 or Ps (which is highlighted in red), what is true about all values less than Ps. L=00000000.0, a. We carried out 4 swaps prior to iteration Ps. 5. What is the bestcase runtime of insertion sort? b. All values prior to position ps have now been sorted. a. O(log n) b. O(n) 2. Given the below details about an intermediate step in insertion sort execution on a particular list input L, how many swaps will be necessary to ensure that all values preceding 14 and 64 are sorted after 14 and 6 are swapped. c. O(n log n) d O(nº) L = (1,3,7, 13, 14, 6.4, 11, 15, 19) 6. Describe why you selected the bestcase runtime ab Provide a sample list of length 5 that would be consider bestcase when we are sorting natural numbers in ascer order. d. 4 3. What is the worstcase runtime of insertion sort? a. O(log n) b. O(n) loon

Answer 1

Please do understand my concern, as per HOMEWORKLIB RULES we are supposed to answer the first question if there is more than one question in a post, your downvote effects my career a lot, if I get a downvote for a wrong answer or incomplete answer I will accept it. Please give a positive rating

1)

a) as we are doing the insertion sort

let p1,p2,p3,p4 are 1,2,3,4 respectively then there are no swaps done, so it is not always mandatory that there will be 4 swaps prior to iteration 5

b) in the insertion sort the loop invariant is the if x is the iterator then all the elements prior to x are always in a sorted manner

since now we are at p5 all the elements before p5 are sorted