Probabilistic selection algorithm

Question

Given is:

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

Find an algorithm that:

• Returns (a close approximation of)the K-th smallest array element.
• Has a runtime complexity of O(N log N) and a space complexity of O(log N).
• The algorithm needn't be deterministic. In case of a probabilistic algorithm also provide a measure for the quality of the approximated result.

• payne: Please add more information. What's the "selection algorithm" being modified? Also, if it's homework you should tag it as such.
• Algos: Selection algorithm is an algorithm to select kth order element in an array without sorting it.
• Stephen C: @Algos - is this homework? (If it is, then I'm sure that the point of it is to get you to work the answer out for yourself.)
• Algos: yes its a homework.. stuck thr for a long time .. so I was looking for some hint .
• Algos: we need a randomized algorithm with O (n log n ) time in high probability

Answer 1

Treat the problem as something analogous to Quicksort. Given an element in the array, you can get its rank in O(n) time and O(lg n) space. You can use binary search to find an element with a given rank in O(lg n) iterations of that, for a total of O(lg n) space and O(n lg n) time.

• Algos: How to get rank of an element in O(n) in case of read only ?. the problem is to get the rank of an element in (n log n ) time.
• Jeremiah Willcock: @Algos: You can get the rank of a given element in O(n); getting an element with a given rank is what we are trying to solve.
• Algos: yep .. got that .. can you explain further the algorithm. still somewhat confused.
• Jeremiah Willcock: @Algos: Assume rank 0 is the smallest array element. Get the largest and smallest elements of the array (call them lo and hi) and their ranks (lo_rank and hi_rank). Label A: Then, pick some element m between lo and hi (in O(n) time) and compute its rank m_rank (in O(n)). If m_rank == k, we are done. If m_rank < k, replace lo and lo_rank with m and m_rank respectively and go to A; if m_rank > k, do the same with hi and go to A.
• Algos: by rank do you mean thr index ?? min element will have rank 0 & max with rank n.

Answer 2

1. Iterate over the array once to find the minimum and maximum element.
2. Iterate over the array to find a random element pivot between minimum and maximum (exclusive).
3. Iterate over the array and count the number of elements less than or equal to pivot (numSmallerEqual) and the number of elements greater than pivot (numBigger).
   1. If K <= numSmallerEqual, set maximum=pivot.
   2. Else set minimum=pivot.
4. If (maximum - minimum)==0, output minimum, terminate.
5. If (maximum - minimum)==1
   1. If K <= numSmallerEqual, output minimum.
   2. Else output maximum.
   3. Terminate.
6. GOTO 2:

EDIT: Corrected the error pointed out by lVlad, still not tested.

• corsiKa: This in fact does not require O(lg n) space as restrained, but O(1). Very nice!
• IVlad: Except it's wrong. 1 3, k = 2. pivot = 2, minimum = 1, maximum = 3, numSmallerEqual = 1, minimum = 2. pivot = 2, numSmallerEqual = 1, minimum = 2 ... infinite loop.
• IVlad: @Dave - I would have suggested a fix if I had one. I'm not sure how to avoid the infinite loop.
• IVlad: I haven't given a lot of thought to the correctness of your updated algorithm, but it's worth pointing out that it doesn't really follow the requirements. The complexity is O(n log v), where v is the difference between the maximum and minimum values of the array, not O(n log n). v can be independent of n.
• Aryabhatta: Why did you change the question?

Answer 3

Don't construct partitions. Describe what the partitions are (in constant space), and recursively select on this.

Each subarray that quickselect recurses into can be described by its bounds (min and max element values, not their indexes). Iterating over a subarray so described requires O(n) comparisons, which are made at every recursion level, up to the same depth as in quicksort: O(log n) in the average case.

Quicksort also makes O(n) comparisons at every recursion level, while ordinary permuting quickselect makes O(n) comparisons in total in the average case (because it always recurses into only one partition).

Here's a sample implementation for distinct elements with an ordinary quickselect implementation for comparison.

• aaz: @Moron – You want O(1) per iteration. "Numbers less than a given element."
• aaz: @Moron – You recurse on all the elements less than the one at rank 100. Say you then find one at rank 50. You recurse on all the elements between the one ranked 50 and the one ranked 100. Iteration, instead of being free, now uses 2*n comparisons per recursion.
• aaz: @Moron – That's not my assumption, and I don't need a contiguous subarray. lo and hi are element values. I will iterate over all n elements of the original array in each step, but I will ignore those x that don't satisfy lo ≤ x ≤ hi.
• aaz: @Moron – Only an intuitive one. Randomized quickselect uses O(n) comparisons per step and recurses an expected O(log n) times, giving O(n log n) runtime. This uses an extra 2 n comparisons per step and recurses exactly like quickselect, so it's still O(n log n).
• aaz: @Moron – You're right. I was thinking that quickselect performs the same as quicksort (expected O(n log n) comparisons). So my algorithm uses more comparisons than quickselect, but approximately the same number of comparisons as quicksort, which Wikipedia says is expected O(n log n). Maybe "with high probability" from the question means "low probability of worst-case behaviour"? Also my algorithm uses only constant space (one recursion which is a tail call), so it's probably not the required answer.

Answer 4

You can take the parameterization approach:

Since we have k specified in the problem, we can treat it as a constant, thus space of O(k log N) should be acceptable.

1. Divide the array into k partitions of equal length (O(1) time and O(k log N) space to store the partition borders because each key should only require log N space)
2. Find the smallest element in each partition (O(N) time and O(k log N) space to store the smallest elements
3. return the max of the k elements you have (O(k) time)

Since there's room for more cycles in there, there's probably a better way to do it. Also note that this would perform very poorly on an array that is sorted...