Given an array A of integers, implement a program that finds the ith largest element in...

Transcribed Image Text:

Given an array A of integers, implement a program that finds the ith largest element in the array. For example. A = [3, 2, 1, 2, 4], i = 2, the element should be 3. If A = [3, 2, 1, 2, 4, 4, 9, 8], i3, the output should be 4. In this problem, you are asked to solve the problem without sorting the input array. Your solution should not use any algorithms from the standard library (e.g.. std: :nth_element). Your implementation should run in expected linear time (Hint: RANDOMIZED-SELECT.) Given an array A of integers, implement a program that finds the ith largest element in the array. For example. A = [3, 2, 1, 2, 4], i = 2, the element should be 3. If A = [3, 2, 1, 2, 4, 4, 9, 8], i3, the output should be 4. In this problem, you are asked to solve the problem without sorting the input array. Your solution should not use any algorithms from the standard library (e.g.. std: :nth_element). Your implementation should run in expected linear time (Hint: RANDOMIZED-SELECT.)

Answer rating: 100% (QA)

import random def randomizedselect A i left ... View the full answer