Hello, I've been trying to figure this out but im missing something Given an unsorted array A[0...n-1] of different integers, find the k-th smallest element (with k=0 being the smallest element). For example, findKth( [ 8 9 5 6 3 11 ] , 0) = 3 and findKth([ 2 6 5 4 13 10 ] , 4 ) = 10.
Complete the following pseudocode for the findKth algorithm. The algorithm should have similarities to quickSort and to binarySearch & should call the partition algorithm used by the quickSort method. You can call the partition without redefining it. Running time should be in O(n) Algorithm partition(A, start, stop) Input: An array A, indices start and stop. Output: Returns an index j and rearranges the elements of A such that for all i<j, A[i] <= A[j] and for all k>i, A[k] >= A[j]. pivot <- A[stop] left <- start right <- stop - 1 while left <= right do while left <= right and A[left] <= pivot) do left <- left + 1 while (left <= right and A[right] >= pivot) do right <- right -1 if (left < right ) then exchange A[left] <-> A[right] exchange A[stop] <- A[left] return left heres an example A = [ 6 3 7 3 2 5 7 5 ] pivot = 5 A = [ 6 3 7 3 2 5 7 5 ] swap 6, 2 A = [ 2 3 7 3 6 5 7 5 ] A = [ 2 3 7 3 6 5 7 5 ] swap 7,3 A = [ 2 3 3 7 6 5 7 5 ] A = [ 2 3 3 7 6 5 7 5 ] swap 7,pivot A = [ 2 3 3 5 6 5 7 7 ] see all on the left are smaller than 5 and all on the right are higher or equal to 5 When i call the partition function it will give me the left side of the pivot... 3 in this example and then i guess if the number given to me is less than k then i need to somehow resort only the left part and if its bigger than the number returned do something with the right part or something like that... iv been trying to figure this out but i cant :( any help will be really appreciated. a few hints or something will be great --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
