9. [5] Consider the following variation of PARTITION (for Quicksort) due to N. Lomuto. To partition...

 

Transcribed Image Text:

9. [5] Consider the following variation of PARTITION (for Quicksort) due to N. Lomuto. To partition A[p..r], this version grows two regions, A[p..i] and A[i+1..j] such that every element in the first region is less than or equal to x= A[r] and every element in the second region is greater than x. LAMUTO-PARTITON(A.p.r) x ← A[r] itp-l for jp to r do if A[j] ≤ x then i ←i+1 ifi<r exchange A[i] A[j] then return i else return i-1 ( a. [2] Show that LOMUTO-PARTITION is correct using an example (array) below: 2 5 7 10 6 b. [3] What is the running time of the algorithm on n-element subarray? 8 9 9. [5] Consider the following variation of PARTITION (for Quicksort) due to N. Lomuto. To partition A[p..r], this version grows two regions, A[p..i] and A[i+1..j] such that every element in the first region is less than or equal to x= A[r] and every element in the second region is greater than x. LAMUTO-PARTITON(A.p.r) x ← A[r] itp-l for jp to r do if A[j] ≤ x then i ←i+1 ifi<r exchange A[i] A[j] then return i else return i-1 ( a. [2] Show that LOMUTO-PARTITION is correct using an example (array) below: 2 5 7 10 6 b. [3] What is the running time of the algorithm on n-element subarray? 8 9

Answer rating: 100% (QA)

a Consider the given example 2 5 8 3 9 4 1 7 10 6 i j 6 is the pivot 2 5 3 8 9 4 1 7 10 6 i j Part... View the full answer