The simple way is to recursively call the partitioning function on the left or right part of the vector according to the current pivot and k until they coincide. But this has only EXPECTED TIME complexity O(n) and in the worst case it is just O(n^2). That appens 'cause partition doesn't assure a balanced subdivision. To balance it you must do something a bit different. You have to break your vector in n/5 vector of length 5; then you have to sort these small vectors (let's say with InsertionSort) and take the median of each of them. Than you have n/5 medians: find the median of the medians applying recursively findKth(). Call partition taking the median of the medians as pivot. Do it (recursively) until the pivot is your k-th boy. It turns out that this procedure as linear worst time complexity (observe that sorting five elements takes O(1) 'cause the length of the input is constant...)
This algorithm is due to Blum Floyd Pratt Rivest and Tarjan. --~--~---------~--~----~------------~-------~--~----~ 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-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
