refer to this link <http://www.ics.uci.edu/~eppstein/161/960130.html>. or Using quicksort , it can be done in O(n). One more way to do this is to make min heap of size-k. Then insert elements from the original array.If element is greater than root of the heap,swap them.In the Last, root of the heap would be the kth smallest element
On Wed, Jun 20, 2012 at 8:47 PM, ajeet <[email protected]> wrote: > Hi, > > It looks like, The interviewer is expecting MinHeap from you, > > If modification to array is permitted just build the heap in place (from > end bubbleUp n-1 time).... and extract K elements in sorted order.... > Otherwise you need minimum O(K) memory > > Again if you want to use the quick-sort, I would prefer only using > partition part of quick sort.. > 1. Select any pivot 'P' > 2. Partition the array.. > 3. position of the pivot p > 4. if p < k ( kth min lies on left part) repeat again for k > 5 if p > k ( kth min lies on right part) repeat again for k-p > 6 if p = k ( You are lucky) exit > > Again in worst case it is o(N2) > > -Ajeet > > Thanks > -A > > > On Wednesday, 20 June 2012 00:56:36 UTC+5:30, adarsh kumar wrote: >> >> This can be done using the concept of median of medians, wherein we can >> achieve linear time complexity in the worst case. >> This is a concept used in parallel algorithms too, check it out. >> >> On Mon, Jun 18, 2012 at 5:38 PM, Prem Nagarajan >> <[email protected]>wrote: >> >>> @enchantress : This problem can be solved using quicksort in O(nlogn). >>> No need to go for selection sort. >>> But O(n) solution is needed. >>> >>> >>> On Mon, Jun 18, 2012 at 2:50 PM, enchantress <[email protected]>wrote: >>> >>>> >>>> Hi all, >>>> A variation of selection sort can be used which takes O(nk) time. >>>> >>>> for i 1 to k >>>> min_index = i >>>> for j i+1 to n >>>> if a[j] < a[min_index] >>>> min_index = j >>>> swap(a[i],a[min_index]) >>>> >>>> required element : a[k] >>>> >>>> On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: >>>> >>>>> Give an array of unsorted elements, find the kth smallest element in >>>>> the array. >>>>> >>>>> The expected time complexity is O(n) and no extra memory space should >>>>> be used. >>>>> >>>>> Quickselect algorithm can be used to obtain the solution. Can anyone >>>>> explain how quickselect works? >>>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To view this discussion on the web visit https://groups.google.com/d/** >>>> msg/algogeeks/-/FABBRabzVqMJ<https://groups.google.com/d/msg/algogeeks/-/FABBRabzVqMJ> >>>> . >>>> >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@** >>>> googlegroups.com <algogeeks%[email protected]>. >>>> For more options, visit this group at http://groups.google.com/** >>>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>. >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to algogeeks+unsubscribe@** >>> googlegroups.com <algogeeks%[email protected]>. >>> For more options, visit this group at http://groups.google.com/** >>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>. >>> >> >> -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/sBvT2ztJpoUJ. > > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
