Help with Algorithm homework 5. If the Stooge-Sort algorithm is applied to the i
ID: 3848236 • Letter: H
Question
Help with Algorithm homework
5. If the Stooge-Sort algorithm is applied to the input list (6, 5, 3, 4, 1, 2) how many
exchanges are performed between elements in this input list? List each swap in the order in which it is made during the execution of the algorithm.
6. Consider the Merge-Sort algorithm presented in class. Which permutation of the input list (1, 2, 3, 4, 5, 6, 7, 8) will elicit the best-case performance (as measured in number of comparisons) between elements in the input list. We do NOT count comparisons to sentinels. Also, answer the same question for worst-case.
Explanation / Answer
1. Stooge sort has three major steps:
a. if last element is less than first element, swap.
b. call stooge sort recursively on intial 2/3 of array
c. call stooge sort recursively on last 2/3 of array
d. again stooge sort recursively on initial 2/3 of array.
The function can be written as
7 swaps. list of swaps in order of algo are:
swapped 6 2, from step(a)
[2, 5, 3, 4, 1, 6]
swapped 5 3
[2, 3, 5, 4, 1, 6]
swapped 5 4
[2, 3, 4, 5, 1, 6]
swapped 4 1
[2, 3, 1, 5, 4, 6]
swapped 5 4
[2, 3, 1, 4, 5, 6]
swapped 2 1
[1, 3, 2, 4, 5, 6]
swapped 3 2
[1, 2, 3, 4, 5, 6]
2. The complexity of merge sort is always O(nlogn). However in practice, the running time also depends on the number of comparisons made in the merge step of the algorithm. If we have to merge {1,2,3,4} {5,6,7,8}, The number of comparisons are : 1 and 5, 2 and 5, 3 and 5, 4 and 5. ie 4.
When we merge {1,3,5,7} and {2,4,6,8}, ie alternate elements are in different halfs, then comparisons are 1 and 2, 3 and 2, 4 and 3, 5 and 4, 6 and 5, 7 and 6, 7 and 8. 7 comparisons. So, keeping this in mind,
best case will be {1,2,3,4,5,6,7,8}.
Worst case will be {1,5,3,7,2,6,4,8}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.