18 8 3 2 1 5 4 9 10
Suppose we want to know the k-th element of the array, how we would do?
- We would sort the array, with O(nlogn) for example
- Then we will get the element searched
But there’s a faster method using a similar idea of QuickSort. Let’s view the QuickSelect algorithm in pseudocode applied to the problem of find the kth element of an array.Integer KthElement(Sequence S, Integer k)
Integer KthElement(Sequence S, Integer k)
if length(S) <= 1 return 0
m <- choosePivotPosition(S)
L <- new empty sequence
G <- new empty sequence
E <- new empty sequence
(L,G,E) <- partition(S,m)
if length(L) == k - 1
return E[0]
if length(L) < k - 1
r <- KthElement(G, k - lenght(L))
if length(L) > k - 1
r <- KthElement(L, k)
return r
The idea is:
- Choose a random position in the array
- Partition the sequence in three sub-set: L of the elements that are Less of the element chosen, G of elements that are Greater and E of elements that are Equal
- Then if the L set has just k - 1 elements, in the E set we have the kth element anche we can return it
- Else we have other 2 possibilities: L is greater than our k or less, in both cases we run recursively but we will enter only in one of this two ways because if the L set is smaller than k it makes no sense to search the kth element there, so let's search only on the greater set (setting k passed as parameter opportunely) and vice versa
- Finally return the result of the recursive call
Note that this algorithm does not handle the case in which we have repetition in the array, as for example:
7 12 15 2 4 2 1 4 2
In this case the first step will do (chosen 12 for example)
7 2 4 2 1 4 2 -- 12 -- 15 ^----- L ---^ E G
If we want to search for the 8th element of the array the repetition of 2 and 4 in the L set will alter the result because the algorithm at the first step, because L is 7 elements big, will return 12 as the 8th element while if we ordered the array
1 2 2 2 4 4 7 12 15 1 2 --- 3 - 4 5 6th
there's no 8th element!