3. Consider the following sorting algorithm: First sort the first two thirds of

Question

3. Consider the following sorting algorithm: First sort the first two thirds of the elements in the array. Next sort the last two thirds of the elements of the array. Finally, sort the first two thirds again. (After each two-thirds sort, the relevant elements are stored in the same two thirds of the array were they resided before the sort; no extra storage is allocated.)
(a) Give an informal but convincing explanation (not a rigorous proof by induction) of why this algorithm returns a fully sorted array.
(b) Find a recurrence relation for the worst-case running time of this algorithm, then solve it by applying the Master Theorem.

Explanation / Answer

stoogeSort (A,i,j)

if A[i] > A[j]

swap A[i] and A[j]

if i + 1 j

return

k = b(j i + 1)/3

stoogeSort(A, i, j k)

stoogeSort(A, i + k, j)

stoogeSort(A, i, j – k)

The recurrence is T (n) = 3T (2n=3) + O(1), since we split arrays into three smaller arrays, each of size 2/3 the size of the big array the nonrecursive portion of the code is O(1) (i.e., the complexity is bounded by a constant).

By the Master Theorem (with a = 3, b = 3=2, and = log3/2 3, say), T (n) (nlog3/23). Now, to compute log 3/2 3, observe that it is equal to loge 3/ loge(3/2) ( 2:71). Thus, since 2:71 > 2:7, we can say that T (n) (n2.7). The worst-case running time of Stooge sort is worse than all worst-case running times of insertion sort ( (n2)), merge sort ( (nlgn)), quicksort ( (n2)) and heapsort ( (nlgn)).

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

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