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 [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.
