Although we focused on Quicksort as a randomized sorting algorithm, randomized c

Question

Although we focused on Quicksort as a randomized sorting algorithm, randomized can be applied to almost any sort. For this problem, consider Insertion Sort. At any point during Insertion Sort, a subarray is sorted, and the rest of the array is not-yet-sorted. The sorted subarray starts out empty, the not-yet-sorted subarray is the whole input, and the algorithm proceeds as follows:

Select the left-most element from the not-yet-sorted subarray

Iterate through the sorted subarray, right-to-left, until you find the correct position for the current element

A

What could an adversary do to an input array to trigger Insertion Sort’s worst-case run-time?

B

How would you randomize insertion sort? Pseudocode is not required here, just a description of what would be randomized.

C

Now let’s evaluate the expected run-time of randomized insertion sort. As with quicksort, the expected run-time depends heavily on the number of total comparisons made. Let X represent the number of comparisons. Let Xi,j be an indicator random variable with value 1 if i is compared to j and 0 otherwise. Find E[X], the expected number of comparisons made overall.

Explanation / Answer

A.

Worst case analysis of insertion sort can be a descending order number series. As if numbers are in descending order then you need to shift (i-1) numbers in ith iteration hence T(n) = sum(i-1) for i in range(1,n) = n*(n-1)/2 = O(n^2)

·         For the first item, 0 comparisons are made.

·         For the second item, it is compared to the first item and find that they are not in the right position; 1 comparison has been made.

·         For the third, it is compare it with both, and found that the third has to go to the top. So 2 comparisons.

·         This goes on; for every following value, you make one more comparison.

·         Finally, for the nth item, you make n - 1 comparisons.

B.

Method to randomize insertion sort is by either prior to calling insertion sort, or during insertion sort, insert a random element this makes the runtime depend on a probabilistic experiment

C.

                                                E(Xi) = j xijp(xij )

Where E(Xi) is the expected value Xi

And, p(xij) is the probability of inserting xi in the jth position 1ji

Hope your question has been resloved now. Please do not forget to give a positive like to the answer. Thank you.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.