Probability Choice Algorithm

Question

Given:

• Array of length N
• The array contains integers.
• Integers are not necessarily sorted.

Find an algorithm that:

• Returns (close approximation) the Kth smallest element of an array.
• It has O ( N log N ) execution complexity and O (log N ) space complexity.
• The algorithm should not be deterministic. In the case of a probabilistic algorithm, a measure of the quality of the approximate result is also provided.

Answer 1

Think of the issue as something similar to Quicksort. Given an element in an array, you can get its rank at O ​​(n) time and O (log n). You can use binary search to find an element with a given rank in O (log n) iterations of this, for the total number O (log n) and time O (n log n).

Answer 2

Do not create partitions. Describe that sections (in constant space), and recursively select on this.

Each subarray that quickselect recurses into can be described by its boundaries (min and max values, not their indices). Iterating over the submatrix described below requires O (n) comparisons that are performed at each recursion level, to the same depth as in quicksort: O (log n) in the average case.

Quicksort also does O (n) comparisons at each recursion level, while the usual quickselect permutation does a general O (n) comparison in the middle case (because it always only rewrites in one section).

Here's an example implementation for individual elements with the usual quickselect implementation for comparison.

Answer 3

• Navigate the array once to find the minimum and maximum element.
• Let's move on to the array to find a random pivot element between minimum and maximum (exclusive).
• Iterates through the array and counts the number of elements less than or equal to pivot ( numSmallerEqual ), and the number of elements greater than pivot ( numBigger ).
  • If K <= numSmallerEqual , set maximum = pivot.
  • Else set minimum = pivot.
• If ( maximum - minimum ) == 0, the minimum output completes.
• If ( maximum - minimum ) == 1
  • If K <= numSmallerEqual , print minimum .
  • Else output maximum .
  • Abort.
• GOTO 2:

EDIT: Bug fixed by lVlad, still not tested.

Answer 4

You can use parameterization:

Since we are given in problem k , we can consider it as a constant, therefore, the space O ( k log N ) is admissible.

• Divide the array into k sections of equal length (O (1) and O ( k log N ) times) to preserve the section boundaries, because each key only needs a log N space)
• Find the smallest item in each section (O ( N ) and O ( k log N ) times) to store the smallest items
• return the maximum number of k elements that you have (time O ( k ))

Since there is room for more cycles, perhaps the best way to do this. Also note that this will do very poorly in a sorted array ...