Provide pseudo-code for an in-place (no extra storage) algorithm to take an arra

Question

Provide pseudo-code for an in-place (no extra storage) algorithm to take an array of n integers and rearrange it such that all of the even numbers occur before any of the odd numbers. What is the worse case runtime complexity of your solution to problem 1? What Ls the average case runtime complexity of your solution to problem 1? Is your solution to problem 1 "stable", in the sense that values with the same parity will not be exchanged? Does your solution in problem 1 remind you of any sorting algorithm that we have studied? If so, explain any difference in the average runtime complexity between the sorting algorithm and problem 1. Provide pseudo-code using a dynamic programming algorithm for the evaluation of the number of combinations of n items taken k at a time. Use the following recurrence relation: Please write pseudo-code (not Java). No variable declarations, output statements or semi-colons needed. Given the following array A[1 hellips 10]: 13 3 39 1 30 *5 29 7 24 11 Show the array after it has been "heapified". After the maximum value (39) has been moved to A[10] and the heap has been "re-heapified". After the next largest element has been moved to A[9] and the heap has been re-heapified". A radix sort has runtime complexity of Theta(nd) where n is the number of ralues and d is the number of digits in each key. This is typically much better than the Theta(n lg n) performance of either Quicksort or Heapsort. Is there some drawback to radix sorting that prevents it from widespread use?

Explanation / Answer

(1)
divider=0
FOR I=0 to n-1 do:
   IF arr[I] is even
       SWAP( arr[divider] , arr[I] )
       divider++
   END-IF
END-FOR   

(2)
Worse case run time complexity:
since for loop will execute n times,complexity will be O(n)

(3)
Average case runtime complexity:
Since best case and worst case complexity is same thart is O(n)
hence avg case will also be O(n)

(4)
Yes,rearrangement of elements is stable since position's of elements of two equal values will not be exchanged.First element will always be first element.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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