In this question we wish to develop a variant of the PARTITION procedure which w
ID: 3861465 • Letter: I
Question
In this question we wish to develop a variant of the PARTITION procedure which works as follows. PARTITION here is to choose the last element as pivot, permute the input array A[p, . . . , r] and return two indices q and t such that: • q is the final index of the pivot, and p q t r • All elements of A[p, . . . , q] are equal • A[q + 1, . . . , t] < A[q] • A[t + 1, . . . , r] > A[q]
(a) (10%) Develop the PARTITION pseudo-code associated with the above strategy. Your PARTITION procedure should run in (n) time, where n is the length of the input array. No credit will be given otherwise.
(b) (10%) Develop the corresponding QUICKSORT that is associated with this PARTITION function.
(c) (10%) Is the resulting QUICKSORT stable? Prove your answer or else provide a counter-example.
Explanation / Answer
part A
- foo(int A[] , int p , int r){
int q =p, t=p
swap A[p] and A[r]
for i=p+1 to r {
- if A[q] > A[i] {
- swap A[t+1] and A[i]
- t=t+1 }
- else if A[q] == A[i] {
- swap A[t+1] and A[i]
- swap A[t+1] and A[q+1]
-q=q+1
-t=t+1 }
}
return (q , t)
}
part B
quickSort (int A[ ] , int i, int j) {
if i >= j
return
( a, b ) = foo(A , i , j)
quickSort( A, a+1 , b)
quickSort( A, b+1, j)
for i=0 to b-a-1 {
swap A[i] and A[i+a+1]
}
}
part C
- Nopes the given algorithm is not stable and the only thing doing this is line no 2 in parA (function foo). As for eg:
inital array is let 3 at A[0] correspond to x and 3 at A[n-1] correspond to y
3 5 6 2 1 3
(x) (y)
after calling foo it becomes
3 3 2 1 3 6 5
(y) (x)
y and x interchanges that key with same value iterchange position and after sorting this will remain in the same
y , x order . so unstable sorting
But this can be converted to stable by just tweaking foo function which you can try yourself.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.