[Solved] Cpt S 350 Homework #2

Please print your name!

1. (easy) Write psuedo-code for partition(A,p,q).
2. (standard) Consider insertsort. Suppose that the input array A has 1% probability to be monotonically decreasing. Show that, in this case, the average-case complexity of insertsort is (n²).
3. (not hard) Let iqsort(A,1,n) be an algorithm that sorts an array A with n It works as follows:

iqsort(A,p,q){ if p q, return; r=partition(A,p,q);

//run quick sort on the low part quicksort(A,p,r 1); //run insert sort on the high part insertsort(A,r + 1,q);

}

Compute the best-case, worst-case, and average-case complexities of iqsort.

4. (hard) Let mixsort(A,1,n) be an algorithm that sorts an array A with n It works as follows:

mixsort(A,p,q){ if p q, return; r=partition(A,p,q);

//run mixsort on the low part mixsort(A,p,r 1);

//run insert sort on the high part insertsort(A,r + 1,q);

}

Compute the best-case, worst-case, and average-case complexities of mixsort.

1