Consider the following cruel and unusual sorting algorithm. (better formatting a

Question

Consider the following cruel and unusual sorting algorithm.

(better formatting at http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/hwex/f13/hw1.pdf )

question:

1. describe the recurrence and runtime relationship for both algorithm

2. Prove that CRUEL correctly sorts any input array.

3. what is the complexity class of both sorting algorithm

CRUEL(A1..n1: if n>1 CRUEL(A[1..n/2]) CRUEL(An/2+1..n]) UNUSUAL(AT1., n): If n = 2 if A[1]> A[2] (the only comparison! swap A[ 1]-A[2] else for l 1 to n/4 swap 2nd and 3rd quarters swap A[i + n/4] A[i + n/2] UNUSUAL(A[1..n/2]) UNUSUAL AIn/2+1..n]) recurse on left half) recurse on right half recurse on middle half

Explanation / Answer

1. cruel(n) = cruel(n/2) + cruel(n/2) + unusual(n)
unusual(n) = O(n/4) + 3*unusual(n/2)

2 . Unusual(n) = takes two sorted components and merges into one .

Each component divides into two halves - lowerhalf and upperhalf.

Compares the lower and upper of both components separately .

Say Cruel(n) = sorts an array on n numbers , then

according to algorithm , crule(n/2) = sorts an array of n/2 integers .

Sorts , lower and upper half . and then merges it using unusual(n)

3. Time complexity of both the algorithms

unusual(n) = n/4 + 3*[n/2 + n/4 + ... ]
= n/4 + 3*(n) = O(n)
cruel(n) = 2*cruel(n/2) + O(n)
= O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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