There is a sorting algorithm, “Stooge-Sort” which is named after the comedy team
ID: 3765253 • Letter: T
Question
There is a sorting algorithm, “Stooge-Sort” which is named after the comedy team, "The Three Stooges." if the input size, n, is 1or 2, then the algorithm sorts the input immediately. Otherwise, it recursively sorts the first 2n/3 elements, then the last 2n/3 elements, and then the first 2n/3 elements again. The details are shown in Algorithm below.
Algorithm StoogeSort(A, i, j ):
Input: An array, A, and two indices, i and j, such that 1 <= i <= j < n
Output: Subarray, A[i..j] ,sorted in nondecreasing order
n <- j – i + 1 // The size of the subarray we are sorting
if n = 2 then
if A[i] > A[j] then Swap A[i] and A[j]
else if n > 2 then
m <- (floor function) n/3(floor function)
StoogeSort(A, i, j-m) // Sort the 1st part.
StoogeSort(A, i+m, j) // Sort the last part.
StoogeSort(A, i, j-m) // Sort the 1st part again.
return A
1. Show that Stooge-sort is correct by Mathematical Induction
2. Characterize the running time, T(n) for Stooge-sort using as recurrence equation.
3. By means of Master's Method, determind an asymptotic bound for T(n)
4. Solve the recurrence equation in 2. by meas of 'Ierative Substitution' method.
Thank you for your help!!!!
Explanation / Answer
There is a sorting algorithm, “Stooge-Sort” which is named after the comedy team
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.