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 <prem.cmna...@gmail.com>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 <elaenjoy...@gmail.com>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. >>> >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> 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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
