## Quickselect algorithm

1 |
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)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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:

1 |
7 12 15 2 4 2 1 4 2 |

In this case the first step will do (chosen 12 for example)

1 2 |
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 |
1 2 2 2 4 4 7 12 15 1 2 --- 3 - 4 5 6th |

there’s no 8th element!