data structures - Quick sort partitioning algorithm.How it works -

data structures - Quick sort partitioning algorithm.How it works -

this algorithm partitioning in quick sort.

let a=x[lb] (lb refers lower bound) element final position sought. 2 references , downwards initialized upper , lower bounds of sub-array respectively. @ point during execution, each element in position above grater a.

two references , downwards moved towards each other in next fashion step 1: repeatedly increment pointer downwards 1 position until x[down] > =

step 2: repeatedly decrease pointer 1 position until x[up] <

step 3: if > downwards interchange x[down] x[up]. process repeated until status in step 3 fails ( i.e =< down) @ point x[up] interchanged x[lb] ( equal a), final position sought , j(i.e final position) set up.

using algorithm have partition array

25,57,48,37,12,92,86,33

pivot selected first element in array. a=25.

initially down=0,and up=7. since status x[down]>=a satisfied downwards pointer doesn't have moved. after decreasing 4 times downwards points 0 , points 4.

then interchanging x[down] x[up]

12,57,48,37,25,92,86,33

after increasing downwards 1 time , decreasing 4 times come up=0 , downwards =1. have interchange x[up] x[lb]. have 12,57,48,37,25,92,86,33 j=up=0.

is correct. ? when applied quick sort algorithm have quicksort(x,1,7).

that have partition array 57,48,37,25,92,86,33

selecting first element pivot a=57.

then down=0,up=6.

interchanging x[down] x[up] 33,48,37,25,92,86,57. repeatedly increasing downwards pointer 4 times , repeatedly decreasing ointer 3 times have 33,48,37,25,92,86,57

then down=4,up=3. interchange x[up] x[lb] have 25,48,37,33,92,86,57 j=up=3.

but this not partitioned correctly around 57.

i can't see error making.therefore if can help me figure out error helpful

after interchanging x[down] x[up] have update downwards , too. step 3 should modified as: step 3: if > downwards interchange x[down] x[up] and down++ , up--. process repeated until status in step 3 fails ( i.e =< down) @ point x[up] interchanged x[lb] ( equal a), final position sought , j(i.e final position) set up.

algorithm data-structures quicksort partitioning