Can someone explain this? I am just confused about what indices do what, in rega
ID: 3888221 • Letter: C
Question
Can someone explain this? I am just confused about what indices do what, in regards to the relationships between p, q, j , and i. I just don't understand what exactly p and q represent. I think i and j are the values around the partition, v. However I am not sure if I am understanding this correctly?
2.3.22 Fast 3-way partitioning. (J. Bentley and D. Mcllroy) Implement an entropy optimal sort based on keeping item's with equal keys at both the left and right ends of the subarray. Maintain indices p and q such that a[lo..p-1] and a[q+1.hi] are all equal to a[lo], hi an index i such that a[p..i-1] are all less than a[lo], SV -V and an index j such that a [j +1.. q] are all greater than 1 a[lo].Add to the inner partitioning loop code to swap a[i] with a[p] (and increment p) if it is equal to v and to swap a[j] with a[q] (and decrement a) if it is equal to v before the usual comparisons of a[i] and a[j] with v. After the partitioning loop has terminated, add code to swap the items with equal keys into position. Note: This code complements the code given in thoe text, in the sense that it does extra swaps for keys equal to the partitioning item's key, while the code in the text does extra swaps for keys that are not equal to the partitioning before V hi after eV >V Bentley-Mcllroy 3-way partitioning item's keyExplanation / Answer
It is a method of quick sort where partioning of array is done into subarrays. Here one pivot a(lo) is taken and i and j are two index pointer taken one (I) at left end (one less than pivot) and second pointer (j) is taken at right end . These two pointer increment untill it crosses each other . P and q are another two pointer which helps in swapping the values from index pointer i and j respectively . There were some rules according to which swapping takes place .
1. Scan a(i) from left to right untill a(i) < a(lo)
2. Scan a(j) from right to left untill a(j) >a(lo)
3 exchange a(I) to a(j) if a(I) >a(lo) and a(j) < a(lo)
4. If a(i) == a(lo) then a(I) swap with a(p) and increment p
5 if a(j) == a(lo) then a(j) swap with a(q) and increment q .
Continue this untill I and j pointer crosses each other.
After they crosses each other then ,
Now swap equal keys to the center as shown in above figure
1. Swap a(j) with a(p) and swap a(I) with a(q) .
Continue till all p and q swap with j and I respectively and it comes to the center.
Now partitioning is done as all smaller values are on left side of the array , equal values at the center and larger at the right end .
I hope u understand any doubt you can comment in the comment box. Thank you