Question

2. Assume you have an input array A with entries numbered 1 through n. One intuitive way to randomize A is to generate a set of n random values and then sort the array based on these arbitrary mumbers. (a) (10 pts) Write pseudocode for this PERMUTE-BY-SorTInG method (b) (10 pts) Do best-, average, and worst-case analyses for this method. (c) Extra credit (15 pts): The algorithm RANDOMIZE-In-PLACE(A) A. length for i 1 to n 1 n= 2 swap Ali with A[RANDOM (i, n)] can permute an array in e(n). Use a loop invariant to show that this algorithm generates a uniformly random sequence

Answer 1

Permute -By-Sorting---It is very ineffective algorithm for sorting an array. It simply permute its inputs until a sorted output is obtained.

Pseudo Code

while not sorted (list)

do{

shuffle(list)

}

Shuffle (list)

{

A for loop[i to length of array]

swap(array[i],array(rand()%n)]

}

b.

Time Complexity--->

1.Worst case is O(infinity) as if after many random permutation array is not sorted

2.Average Case O(n*n!) means n times we are making n! no. of permutation to get a sorted array

3.Best Case O(n) ---if given array is already sorted .

Q2 What is role of function Random(i,n) not mentioned