top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

Finding Kth smallest element in an unsorted Array?

+1 vote
157 views

Given an unsorted array of elements I want to findout the Kth smallest element in the array. Can someone help me with the approach and code.

posted Jul 4, 2014 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes
  1. Divide the array in to n/5 lists of 5 elements each.
  2. Find the median in each sub array of 5 elements.
  3. Recursively find the median of all the medians, lets call it M
  4. Partition the array in to two sub array 1st sub-array contains the elements larger than M , lets say this sub-array is a1 , while other sub-array contains the elements smaller then M., lets call this sub-array a2.
  5. If k <= |a1|, return selection (a1,k).
  6. If k− 1 = |a1|, return M.
  7. If k> |a1| + 1, return selection(a2,k −a1 − 1).

Complexity: o(n)

Source: http://cs.indstate.edu/~spitla/abstract2.pdf

answer Jul 7, 2014 by Salil Agrawal
Similar Questions
+1 vote

Given 3 sorted array of size x, y, z. what is the minimum time taken to find the kth smallest element in the merged sorted array.

+1 vote

Someone asked me this question and I dont have any answer, so thought to ask?

+5 votes

Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

+2 votes

How to find the smallest element in a Binary Tree (Not BST)? Sample C/C++ code would be helpful.

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...