Consider the Partition algorithm we discussed in class. Partition(A)
pivot = A[0], i = 1, j = A. length-1; // Let the leftmost element be the pivot
while i<=j // Rearrange elements
while i < A. length-1 & A[i] < pivot,
i = i + 1
end while
while j > 0 & A[j] >= pivot,
j = j - 1
end while
if i >= j
break
end if
swap A[i] and A[j]
end while
swap A[0] and A[j]
return j; // Return the index of pivot after the partition
Upon completion of the Partition algorithm, the pivot element would be placed in the middle, elements less than pivot are placed on the left of pivot, and elements greater than or equal to pivot are placed on the right of pivot.
Given a list (A) of n elements, outline an O(n) time in-space algorithm based on the Partition algorithm such that upon completion of the algorithm, elements equal to the pivot (including the pivot element) would be placed in the middle, elements less than pivot are placed on the left of pivot, and elements greater than pivot are placed on the right of pivot.
For example, let A be {1, 2, 2, 2, 6, 1, 7, 0, -5, 2, 8, 1, 3, 1, 1}.
Let the first element 1 be the pivot.
If you call the original Partition method on list A, A would become:
{0, -5, 1, 2, 6, 1, 7, 2, 2, 2, 8, 1, 3, 1, 1}.
This problem asks you to design an algorithm, such that list A would become
{0, -5, 1, 1, 1, 1, 1, 2, 6, 7, 2, 2, 2, 8, 3}, such that the pivot 1 and all the other 1’s would be placed in the middle of the array, elements less than 1 would be on the left of all 1’s, and elements greater than 1 would be on the right of all 1’s.
Full credit (10 points) will be awarded for an algorithm that is O(n) and in-place. Algorithms that are NOT in-place or O(nlogn) or slower will be scored out of 3 points.
Note: In-place means no new arrays or extra data structure can be used.
a) describe the idea behind your algorithm in English
b) provide pseudocode
c) analyze its running time