Question

Silly-Sort(A,i,j) if A[i] > A[j] then exchange A[i] and A[j]; if i+1 >= j then return;...

Silly-Sort(A,i,j)
if A[i] > A[j]
then exchange A[i] and A[j];
if i+1 >= j
then return;
k = floor(j-i+1)/3);
Silly-Sort(A,i,j-k);
Silly-Sort(A,i+k,j);
Silly-Sort(A,i,j-k);
(a) Argue (by induction) that if n is the length of A, then Silly-
Sort(A,1,n) correctly sorts the input array A[1...n]
(b) Give a recurrence relation for the worst-case run time of Silly-Sort
and a tight bound on the worst-case run time
(c) Compare this worst-case runtime with that of insertion sort, merge
sort, heapsort and quicksort.

0 0
Add a comment Improve this question Transcribed image text
Answer #1

A.

By induction:
For the base case let n = 2. The first two lines of the algorithm will check if
the two elements are sorted; if not, it exchanges them (and now they are sorted).
The algorithm returns after the following if statement. Thus Silly-Sort sorts
correctly for n = 2.
Assume Silly-Sort correctly sorts an input array of size 2n/3 (you may also
assume that Silly-Sort correctly sorts an array of size k, for any 1 ≤ k < n).
Let A[1..n] be an input array of size n. By the induction hypothesis the first call to
Silly-Sort(A, i, j−k) correctly sorts the first 2n/3 elements, so that the elements
1 . . .n/3 are less than elements (n+1)/3 . . . 2n/3. The call to Silly-Sort(A, i, j−
k) correctly sorts the last 2n/3 elements, so that the elements (n + 1)/3 . . . 2n/3

are less than elements 2(n + 1)/3 . . .n. Also, after this call to Silly-Sort the
elements 2(n + 1)/3 . . .n (the last n/3 elements) are the largest n/3 elements in A.
The last call to Silly-Sort(A, i, j − k) sorts correctly (by induction hypothesis)
the elements 1 . . . 2n/3. These sorted elements are less than elements 2(n+1)/3 . . .n.
Thus the array A of size n is sorted.

b. Give a recurrence for the worst-case running time of Silly-Sort and a tight
asymptotic (Θ-notation) bound on the worst-case running time.
Solution:

T(n) = 3T(2n3) + Θ(1)

= . . .

= Θ(n^log3/2 3)

= Θ(n^2.7...).

c.
Insertion-Sort: Θ(n^2)
Merge-Sort: Θ(n lg n)
Heapsort: Θ(n lg n)
Quicksort: Θ(n^2)
Silly-Sort: Θ(n^2.7...)

Add a comment
Know the answer?
Add Answer to:
Silly-Sort(A,i,j) if A[i] > A[j] then exchange A[i] and A[j]; if i+1 >= j then return;...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT