CMSC351 (Kruskal) Homework 2 Due: Friday, February 15, 2019
1. Assume we are sorting n distinct values. We say that the input is random if each permutation is equally likely. Wallace Loh (who happens be taking this course in his spare time) suggests an alternative definition: An input is random if, for each pair of elements x, y, half the time x is before y (so that half the time y is before x). It is clear that if each permutation is equally likely then the list is random in the sense of Wallace Loh.
We might wonder if the converse holds. In other words, if the list is random in the sense of Wallace Loh, is each permutation equally likely? It is plausable that the converse holds for some values of n and not others. For what values of n does the converse hold? Justify your answer.
2. We can modify Insertion Sort to insert a pair of elements at a time, instead of only one element: Find the larger element of the pair and put it into its proper location in the sorted array using linear search (as in standard insertion sort). Then, starting from where the larger element ended up, put the smaller element into its proper location again using linear search.
(a) Write the pseudo code, using a sentinel, for this algorithm. You may assume that the size of the array is even.
(b) Assume the size of the array n = 4.
i. What is the best-case number of comparisons? Just state the number and show your
input. Otherwise, no justification needed.
ii. What is the worst-case number of comparisons? Just state the number and show your
input. Otherwise, no justification needed.
iii. What is the average-case number of comparisons? Justify. HINT: There are 24 pos-
sible orderings, which is a lot. The calculation is more manageable if you realize that the first pair of elements essentially defines the whole ordering.
(c) Calculate the average case number of comparisons for general n, where n is even. Show your work.
(d) How does the average case number of comparisons compare with the average case of standard insertion sort?