Trace the Partition function on the following array:
[0] [1] [2] [3] [4] [5] [6]
'F' 'K' 'A' 'R' 'C' 'Y' 'G'
Assume that ChoosePivot returns without doing anything (the purpose of the function it to move the pivot to the leftmost position in the subarray, so by doing nothing the leftmost item in the original arra is the pivot be default). What will be the state of the array after the call?
this is what i got.
F K A R C Y G --- F is pivot
--- first unknown is array[1] = points to "k"
--- k belongs to unknown group called S2
F K A R C Y G --- next unknown is array[2] = points to "A"
--- S1 is empty;
--- A belongs in S1, so swap K and A
F A K R C Y G --- next unknown is array [3] = points to "R"
--- R belongs in S2, so do nothing
F A K R C Y G --- next unknown is array [4] = points to "C"
--- C belongs in S1, so swap K and C
F A C R K Y G --- next unknown is array [5] = points to "Y"
--- Y belongs in S2, so do nothing
F A C R K Y G --- next unknown is array [6] = points to "G"
--- G belongs in S1, so swap R and G
F A C G K Y R --- S1 and S2 are determined
--- F is pivot
--- S1 are A C G
--- S2 are K Y R
--- place pivot between S1 and S2
G A C F K Y R is my final.....is this right??? corret me if i'm wrong....plz~~
if it is then i don't see it from the multiple choice??
a) F A C R K Y G
b) C A F R K Y G
c) A C F K R Y G
d) A C F G K R Y
thanks for your help~~
