assume the following list of keys: 7, 28, 31, 40, 5, 20 The first four keys are
ID: 3653167 • Letter: A
Question
assume the following list of keys: 7, 28, 31, 40, 5, 20 The first four keys are in order. to move 5 to its proper position using intersection sort. exactly how many key comparisons are executed ?Explanation / Answer
// Insertion Sort (A,1,n) 1. FOR j ? 2 TO length[A] 2. DO key ? A[j] 3. {Put A[j] into the sorted sequence A[1 . . j - 1]} 4. i ? j - 1 5. WHILE i > 0 and A[i] > key 6. DO A[i +1] ? A[i] 7. i ? i - 1 8. A[i + 1] ? key since we have 4 already sorted elemenrs in using the above pseudocode .. we have i = 4 in step 4 . and our key is 5th element i.e. key = A[5] = 5. first key comparison i = 4 ( i > 0 && A[4] > key ) so i becomes 3 second key comparison i = 3 ( i > 0 && A[3] > key so i becomes 2 third key comparison i =2 ( i > 0 && A[2] > key ) so i becomes 1 fourth key comparison i =1 ( i > 0 && A{i] > key ) so i becomes 0 now i becomes 0 so there will be no key comparison. So total number of key comparison = 4.Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.