SomeSort (A, b, e) if e = b + 1 then if A[b]> A[e] then end...

   

Transcribed Image Text:

SomeSort (A, b, e) if e = b + 1 then if A[b]> A[e] then end if else if e> b+ 1 then Consider the following very simple and elegant(?) sorting algorithm: exchange A[b] and A[e] end if p← [e-b+¹] SomeSort (A,b, e - p) SomeSort (A,b+p, e) SomeSort (A, b, e - p) a. Does SomeSort correctly sort its input array A (assuming that n e-b+1 is the length of the array)? Justify your answer. b. Consider the input array A: 8 1 4 973 2 6 5. List five valid states of the array during the execution of the algorithm. C. Find a recurrence for the worst-case running time of SomeSort. Give a tight (i.e. e) asymptotic bound for the worse-case running time of SomeSort (Hint: consider n = 3k for some k). d. By comparing SomeSort with insertion sort and merge sort, argue if this simple algorithm is efficient. SomeSort (A, b, e) if e = b + 1 then if A[b]> A[e] then end if else if e> b+ 1 then Consider the following very simple and elegant(?) sorting algorithm: exchange A[b] and A[e] end if p← [e-b+¹] SomeSort (A,b, e - p) SomeSort (A,b+p, e) SomeSort (A, b, e - p) a. Does SomeSort correctly sort its input array A (assuming that n e-b+1 is the length of the array)? Justify your answer. b. Consider the input array A: 8 1 4 973 2 6 5. List five valid states of the array during the execution of the algorithm. C. Find a recurrence for the worst-case running time of SomeSort. Give a tight (i.e. e) asymptotic bound for the worse-case running time of SomeSort (Hint: consider n = 3k for some k). d. By comparing SomeSort with insertion sort and merge sort, argue if this simple algorithm is efficient.

Answer rating: 100% (QA)

The images you provided contain an algorithm named SomeSort which is a recursive sorting algorithm and some questions related to it Lets address each part step by step a Does SomeSort correctly sort i... View the full answer