Quickselect Algorithm PLEASE USE PYTHON CODE AND SHOW FUNCTI

Quickselect Algorithm PLEASE USE PYTHON CODE AND SHOW FUNCTION WORKING CORRECT CODE SCREENSHOT A portion of the code has been provided just need the fill in area. Thanks

[Active] Exercise: Quickselect Algorithm Problem statement: n this exercise, you will need to implement the partition function of the quickselect algorithm For the input, you will be given two lines. The first line of input w contain two numbers, n and k, separated by a space: the first number, n, is the size of the list and the second number, k, is the position of the desired number in the sorted list. On the second line of input is where you will be given the list of numbers to manipulate The output should just be ONE integer representing the kth smallest integer in the list given. You are free to modify the starter file as you wish Listed below are some sample inputs and outputs: Input A: 20 4 6 (On the first line, 2 is the size of the list and 0 is the position of the number you need to find in the sorted list. On the second line is the list of numbers given) Output A: (4 is the 0th smallest number based on the list from the input) Input B: 5 3 4 28 01 Output B:

Solution

import sys
from random import randrange
def partition(x, pivot_index):
i = 0
if pivot_index !=0: x[0],x[pivot_index] = x[pivot_index],x[0]
for j in range(len(x)-1):
if x[j+1] < x[0]:
x[j+1],x[i+1] = x[i+1],x[j+1]
i += 1
x[0],x[i] = x[i],x[0]
return x,i
#YOU DO NOT NEED TO CHANGE THE CODE BELOW THIS LINE
def quickSelect(arr,k):
if len(arr) == 1:
return arr[0]
else:
partitioned_arr = partition(arr,randrange(len(arr)))
arr = partitioned_arr[0] # partitioned array
j = partitioned_arr[1] # pivot index
if j == k:
return arr[j]
elif j > k:
return quickSelect(arr[:j],k)
else:
k = k - j - 1
return quickSelect(arr[(j+1):], k)

#Read input
test_values = [int(x) for x in sys.stdin.readline().split()]
n = test_values[0]
k = test_values[1]
numbers = [int(x) for x in sys.stdin.readline().split()]
kSmallest = quickSelect(numbers,k)

print kSmallest

Output refer url: http://ideone.com/xf7l17