Jack loves to play with integers. He created a list of n integers where the even...

 

Transcribed Image Text:

Jack loves to play with integers. He created a list of n integers where the even indices hold numbers in decreasing order and the odd indices hold numbers in increasing order. For example, this is a list of n=8 integers Jack made. Index 0 1 2 3 4 5 6 7 Numb 23 2 19 3 7 11 5 13 er [Explanation: The indices 1, 3, 5, and 7 have numbers 2, 3, 11, and 13 in increasing order. The indices 0, 2, 4, and 6 have numbers 23, 19, 7 and 5 in decreasing order.] You sorted the the list in quadratic time [O(n)]. To your utter surprise, Jack replies, "It could be sorted in linear time". 1) [CO2] Show the steps how you sorted the list using a suitable algorithm. Mention the name of the algorithm. 3 2) [CO2] Describe how Jack sorted the list in linear time. Show the steps too.-4 3) [CO3] Jack wants to add the number 15 to your sorted list from (1). He wants you to come up with an efficient idea about how he is going to find the accurate index position for 15 in the list. Describe how you are going to assist him in this. Show the steps too. 3 - Jack loves to play with integers. He created a list of n integers where the even indices hold numbers in decreasing order and the odd indices hold numbers in increasing order. For example, this is a list of n=8 integers Jack made. Index 0 1 2 3 4 5 6 7 Numb 23 2 19 3 7 11 5 13 er [Explanation: The indices 1, 3, 5, and 7 have numbers 2, 3, 11, and 13 in increasing order. The indices 0, 2, 4, and 6 have numbers 23, 19, 7 and 5 in decreasing order.] You sorted the the list in quadratic time [O(n)]. To your utter surprise, Jack replies, "It could be sorted in linear time". 1) [CO2] Show the steps how you sorted the list using a suitable algorithm. Mention the name of the algorithm. 3 2) [CO2] Describe how Jack sorted the list in linear time. Show the steps too.-4 3) [CO3] Jack wants to add the number 15 to your sorted list from (1). He wants you to come up with an efficient idea about how he is going to find the accurate index position for 15 in the list. Describe how you are going to assist him in this. Show the steps too. 3 -