Given an array and return it in random way.
You are given rand( ) / Which gives a value between 0 and 1
floor( ) → floor(2.88) = 2
INPUT :
1 | 0 | 3 | 9 | 2 |
OUTPUT:
3 | 1 | 9 | 0 | 2 |
rand( ) function selects a value from uniform distribution between 0 and 1
Let’s Multiply 5 X rand( )
Probability of failing a value between 3 and 4 is 20% as each of the value falling probability is 20%
Example:
floor(5 . rand( )) → {0, 1, 2, 3, ,4} (as there are 5 numbers)
So, what will do now, is the following
This process will continue n – 1 times.
For example: float(4 . rand( )) → 1 ∈ {0, 1, 2, 3}
We will choose the value at index 1 i.e. 0 and swap with 3
float(3 * rand( )) → 0 ∈ {0, 1, 2}
float (2 * rand( )) → 1 ∈ {0, 1}
9 | 2 | 3 | 1 | 0 |
float(1 * rand( )) → 0 ∈ {0}
OUTPUT
2 | 9 | 3 | 1 | 0 |
Step 1: Store the length of the array in a variable
Step 2: store the last index in a variable
Step 3: Run a loop from last to the first index
Step 4: Using the given function to find an index and swap it (in place) with
the value at the index in Step 2
Pick = floor((i) * rand( ))
Step 5: Decrease Step 2
Step 6: Repeat from step 3 to step 5 until condition breaks
Step 7: Return the array
Time complexity: O(n)
Space complexity: O(1)