How random quickselect should be implemented and why
Lots of folks without the benefit of nth_element from STL may be wondering how one could implement random quickselect by hand. Random quickselect is very easy t
Lots of folks without the benefit of nth_element from STL may be wondering how one could implement random quickselect by hand. Random quickselect is very easy to implement once you understand the subtleties but it can behave badly on some inputs. (There is a far more complicated worst-case linear-time selection algorithm but it\'s difficult to implement correctly in an interview in my humble opinion). In any case  I\'ve documented my thought process here and explained my understanding of the subtleties with random quickselect, due to the differences of the partitioning algorithm one may choose, (Lomuto or Hoare partitioning); since the go-to partitioning scheme, Lomuto partititoning, will TLE on large array with all same numbers.\n\n```\nclass Solution(object):\n    def getStrongest(self, arr, k):\n        """\n        :type arr: List[int]\n        :type k: int\n        :rtype: List[int]\n        """\n        def lomuto_partitioning(first, last):\n            # Pivot will be some randomly element selected in the range [first, last]\n            # and placed to the end of the array\n            p = random.randint(first, last)\n            pivot = arr[p]\n            arr[last], arr[p] = arr[p], arr[last]\n            \n            # Now we will go through elements in the range [first, last - 1] and place\n            # all those greater than pivot to the right of i, and those less or equal to pivot\n            # to indexes <= i.\n            \n            # Invariant: all elements whose indexes are <= i should be on the left of the pivot\n            i = first - 1\n            for j in xrange(first, last):\n                if arr[j] > pivot:\n                    # keep marching j forward until we find an element <= pivot\n                    continue\n                # Found one, now a[j] <= pivot so it should be at an index <= i. So make room\n                # for it by advancing i and then placing it there\n                i += 1\n                arr[i], arr[j] = arr[j], arr[i]\n            arr[i+1], arr[last] = arr[last], arr[i+1]\n            return i+1\n        \n        def hoare_partitioning(A, first, last, less_than):\n            p = random.randint(first, last)\n            pivot = A[p]\n            A[first], A[p] = A[p], A[first]\n            i, j = first - 1, last + 1\n            while True:\n                i += 1\n                while less_than(A[i], pivot):\n                    i += 1\n                j -= 1\n                while less_than(pivot, A[j]):\n                    j -= 1\n                if i >= j:\n                    # Invariant: all elements in [first, j]  are <= all elements in [j + 1, last]\n                    return j\n                A[i], A[j] = A[j], A[i]\n                \n        def quickselect(A, first, last, i, less_than):\n            if first == last:\n                return first\n            # lomuto partitioning will not do well against input with the same numbers.\n            # (It has O(N^2) behavior in that case)\n            #p = lomuto_partitioning(first, last)\n            # Whereas hoare partitioning will always split non-trivially regardless of the input\n            p = hoare_partitioning(A, first, last, less_than)\n            # Though be aware since hoare partitioning only guarantees that elements in \n            # [first, p] <= [p + 1, last], we cannot follow the standard random-select algorithm \n            # where we do:\n            \'\'\'\n            if first + i == p:\n                  # The element at index first + i is not guaranteed to be the max element amongst\n\t\t\t\t  # those in the range [first, p]\n                  # return p\n            \'\'\'\n            # Instead all we can say is if first + i is at or below index p, we can discard\n            # the right, [p + 1, last], partition\n            if first + i <= p:\n                return quickselect(A, first, p, i, less_than)\n            # Otherwise we can discard the left, [first, p], partition\n            return quickselect(A, p + 1, last, i - (p - first + 1), less_than)\n    \n        n = len(arr)\n        # Use quickselect to find the index of the median. This will have\n        # expected runtime of O(n)\n        median_idx = quickselect(arr, 0, n - 1, (n - 1) / 2, lambda x, y: x < y)\n        median = arr[median_idx]\n        \n        # Use quickselect again to find the index of the k-th (since quickselect() as we\'ve\n        # implemented is 0-indexed, it\'s k-1 th) strongest value. Again it would run\n        # in O(n) time\n        arr_with_strength = [None] * len(arr)\n        for i in xrange(n):\n            arr_with_strength[i] = (abs(arr[i] - median), arr[i])\n        less_than_comparator = lambda x, y: x[0] > y[0] or x[0] == y[0] and x[1] > y[1]\n        p = quickselect(arr_with_strength, 0, n - 1, k-1, less_than_comparator)\n        # Due to how quickselect partitions elements like quicksort, all the elements in the \n\t\t# partition [0, p] should be <= all elements in partition [p + 1, n - 1] where\n\t\t# the ordering defined by the less_than_comparator. (Again this is an invariant \n        # property of Hoare partioning)\n        result = []\n        for i in range(0, p + 1):\n            result.append(arr_with_strength[i][1])\n            \n        # Total runtime is O(n) + O(n) + k => O(n), k is some small constant\n        return result\n```
[]