Search code examples
algorithmsortingbig-oquickselect

Can QuickSelect find smallest element in an Array with duplicate values?

Does the QuickSelect algorithm work with duplicate values?

If I haven an Array

int[] array = {9, 8, 7, 6, 6, 6, 5, 0, 1, 2, 3, 4, 5, 5, 7, 200};

Will it be able to get the kth smallest element even though there are duplicates?

Solution

  • Yes, it works. By the end of every iteration you have all elements less than current pivot stored to the left of the pivot.

    Let's consider case when all elements are the same. In this case every iteration ends up putting pivot element to the left of the array. And the next iteration will continue with one element shorter array. So we need k iterations to find k-th smallest element.