Assignment 2 kth smallest element in an array

Programming Assignment 2

The objective of this assignment is to explore an interesting algorithm known as kth smallest element in
an array.
Problem Definition:
The kth order statistics of an array a of n elements is the kth least element in the array, 𝑘𝑘 = 0, … , 𝑛𝑛 − 1.
Moreover, finding the kth order statistics of a can be accomplished by the following solutions
1- Sorting a and returning the kth element in the sorted array. Using any sorting in 𝑂𝑂(𝑛𝑛 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 )
would do the task!
2- Using Quicksort and reduce the running time for finding the kth statistics down to 𝑂𝑂(𝑛𝑛).
Assignment
1- Implement two algorithms:
a. A min heap, that finds the kth smallest element of a given input array and the value k.
b. Use quicksort (with some modification) to find the kth smallest element of a given input
array and the value k.
2- For both algorithms inputs and outputs are similar. Here are some examples:
a. Example1:
Input: [8, 4, 1, 2, 10] and k = 3
Output: 4
b. Example2:
Input: [7, 10, 4, 3, 20, 15] and k = 4
Output: 10
3- The algorithm for MinHeap can be found from class lecture notes.
4- The following pseudocode can be used for 1-a algorithm. This algorithm uses Quicksort concept
to find the kth element in an arbitrary array.
function kthSmallest(arr, l, r, k)
{
 if (k > 0 and k <= r – l)
q = partition(arr, l, r) // make a partition using the last element
 if (q == k ) // if position is same as k
 return arr[pos]
 if (q > k ) //if position is more, # recur for left subarray
 return kthSmallest(arr, l, q - 1, k)
 return kthSmallest(arr, q + 1, r, k - q + l)
}
Note: You may need to correct the array boundaries for python (e.g. starting from zero)
5- Your program should work for any array, as usual.
What to submit?
1- Write 2 programs for each algorithm. Please name your programs as follows:
a. minheapfind_yourname.py
b. quickfind_yourname.py
2- Your programs should be run as follows:
- minheapfind_youname.py [10,2,3,5] 2 or quickfind_yourname.py [10,2,3,5] 2
The first input is an array and the second input in the value of k
- Both programs return an integer indicating the value of kth smallest element in the list.
Note: make sure test your program for boundary inputs!
3- Please have your name top of your all programs.
4- You should follow general software development rules such as proper and sufficient
commenting if it is necessary and proper functions and variables naming.
5- Do not copy any code from online resources!