Get a value for n the size of the list Get values for A A A

Get a value for n, the size of the list Get values for A A .. A_n the list to be searched Set the value of largest so far to A_1 Set the value of location to 1 Se the value of i to 2 While (i lessthanorequalto n) do If A_i > largest so far then Set largest so far to A_i Set location to i Add 1 to the value of i End of the loop Print out the values of largest so far and location stop Using the Find The Largest Algorithm as shown in figure 2.14 as building blocks, write an algorithm that finds the \"median\" of a list L of n positive elements, where n is odd. (The median is the element that falls in the middle of the list, if the list was sorted. You must not completely sort your list. Your algorithm should be as simple as shown in figure 2.14

Solution

Please find my algorithm.Please let me know in case of any issue.

def median(A, length)

   //odd length array
if length % 2 == 1 then
return quickselect(0, length-1, length/2)
else
lower = quickselect(0, length-1, length/2-1)
higher = quickselect(0, length-1, length/2)
return (lower + higher) / 2.0
end
end

# returns kth smallest element
def quickselect(A, left, right, k):
if left == right
   return A[left]

pivot = (right+1 + left) / 2
new_pivot_index = partition(A, left, right, pivot)
diff = (new_pivot_index - left)

if diff == k
return A[new_pivot_index]
else if k < diff # kth element is in lower partition
return quickselect(A, left, new_pivot_index-1, k)
else # kth element is in higher partition
return quickselect(A, new_pivot_index+1, right, k-diff-1)
end
end
end

def partition(A, left, right, pivot)
pivot_value = A[pivot]
swap(pivot, right)
store_index = left
(left...right).each do |i|
if A[i] < pivot_value
swap(i, store_index)
store_index += 1
end
end
swap(store_index, right)

return store_index
end

def swap(A, from, to)
tmp = A[to]
A[to] = A[from]
A[from] = tmp
end