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~~

What kind of partition function are you using? does "G" appear before "F" in the alphabet?

>Trace the Partition function on the following array
What's the function? There are several ways of partitioning an array, and each algorithm would have a different execution trace.

i guess using the quick sort partition function.

>i guess using the quick sort partition function.
I can think of five different ways, off the top of my head, to implement the partition step of quicksort without affecting correctness or performance. The question in your first post cannot be answered without details of how the algorithm works.