Iterative Algorithm for RANDOMIZED-SELECT

The following algorithm demonstrates an iterative version of the RANDOMIZED-SELECT algorithm. This algorithm returns smallest element in the array A.

In this algorithm,

A - an array of elements

p - lower position of the array

q - higher position of the array

i - position of an element which is to be returned

RANDOMIZED-SELECT(A, p, r, i)

1. while // verify whether the p is less than r, if yes repeat the statements 2 to 8

2. RANDOMIZED-PARTITION(A, p, r) // get partition position

3.

4. if // desired element is at lower side if true

5. // update the value of r

6. else // desired element is at higher side

7. // update the value of p

8.

9. return

Note:

For RANDOMIZED-PARTITION algorithm in the RANDOMIZED-SELECT algorithm, refer the text book, page number - 179.

For PARTITION algorithm in the RANDOMIZED- PARTITION algorithm, refer the text book, page number - 171.

For RANDOM(p, r) in the RANDOMIZED- PARTITION algorithm returns a ranom value between p and r (inclusive), and refer the text book, page number - 117.

In Randomized-Select algorithm, need to select a random number as a pivot point. After selection of randomly pivot point divide the array in two parts the pivot point and the rest of the list.

In the given problem, apply Randomized-Select algorithm in worst case, then the number selected as a pivot will be the maximum number. In this case, each time the randomly selected pivot number will be maximum. And each time array will be divided in two categories pivot number and rest of the list.

Pivot 9 3, 2, 1, 0, 7, 5, 4, 8, 6, || 9

Pivot 8 3, 2, 1, 0, 7, 5, 4, 6, || 8

Pivot 7 3, 2, 1, 0, 6, 5, 4, || 7

Pivot 6 3, 2, 1, 0, 4, 5, || 6

Pivot 5 3, 2, 1, 0, 4, || 5

Pivot 4 3, 2, 1, 0, || 4

Pivot 3 0, 2, 1, || 3

Pivot 2 0, 1, || 2

Pivot 1 0, || 1

Return 0.

It means 0 is the minimum number in the array. In worst case, the Randomized-Select algorithm complexity will be O(n)².