a)Consider the following problem. You are given an array S of n numbers (unsorte

Question

a)Consider the following problem. You are given an array S of n numbers (unsorted), and you are given a value K. You wish to rearrange S such that all the numbers <= K come before the others (other than that, there is no specification for the order of the entries in the output). For example, suppose that K = 10, and S = [4, 40, 5, 2, 11, 9, 12]. Then your output could look something like S = [4, 5, 2, 9, 12, 40, 11]. Design an algorithm to solve this problem, trying to be as efficient as possible. Describe the idea of your algorithm in words, and then also describe it in pseudocode (try to use pseudocode which is similar to that in the book). Note that you cannot use other arrays for this algorithm (i.e. S should be your only array).

b) Do a worst case analysis of your algorithm, counting the number of times you compare two numbers in the array S AND the number of times you compare K to a number in the array S AND the number of times you move a number in S from one position to another. Use n as your input size. Be sure to explain your analysis.

Explanation / Answer

- read array of size n and k

- loop i=0;i<n; n times

in each loop,

compare element with k value

if element <= k

continue

else

loop n-i times (j=n, j--,j>=i

traverse from back to front of array

compare last element with k , if lastelement <= k

swap lastelemnt and element

in worst case,

it wil have n(n+1)/2 + n iterations

in best case n iterations

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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