Question: An alternative permutation algorithm is to fill the array a from a[0] to a[n-1], as follows. To fill a[i], generate random numbers until you get one that has not been used previously. Use an array of Booleans to perform that test. Give an analysis of the expected running time (this is tricky) and then write a program that compares this running time with both your analysis and the routine shown in Figure.
1. /**
2. * Randomly rearrange an array.
3. * The random numbers used depend on the time and day.
4. * @param a the array.
5. */
6. public static final void permute( Object [ ] a )
7. {
8. Random r = new Random( );
9.
10. for( int j = 1; j < a.length; j++ )
11. swapReferences( a, j, r.nextInt( 0, j ) ):
12. }