Quick sort partitioning algorithm.How it works

Question

This is a algorithm for partitioning in quick sort.

Let a=x[lb] (lb refers to lower bound) be the element whose final position is sought. Two references up and down are initialized to the upper and lower bounds of the sub-array respectively. At any point during the execution, each element in a position above up is grater than a.

Two references up and down are moved towards each other in the following fashion
Step 1: Repeatedly increase the pointer down by one position until x[down] > = a

Step 2: Repeatedly decrease the pointer up by one position until x[up] < a

Step 3: if up > down then interchange x[down] with x[up]. The process is repeated until the condition in step 3 fails ( i.e up =< down) at that point x[up] is interchanged with x[lb] ( which equal to a), whose final position was sought and j(i.e final position) is set to up.

Using this algorithm I have to partition the array

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

pivot is selected as the first element in the array. Thus a=25.

Initially down=0,and up=7.
Since the condition x[down]>=a is satisfied down pointer doesn't have to be moved.
After decreasing up 4 times
down points to 0 and up points to 4.

Then interchanging x[down] with x[up] I get

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

After increasing down once and decreasing up 4 times I come up with up=0 , down =1.
Then i have to interchange x[up] with x[lb].
Then I have 12,57,48,37,25,92,86,33 with j=up=0.

Is this correct. ?
Then when applied to quick sort algorithm I then have to do Quicksort(x,1,7).

That is I have to partition the array 57,48,37,25,92,86,33

Selecting first element as the pivot a=57.

Then down=0,up=6.

Interchanging x[down] with x[up] I get 33,48,37,25,92,86,57.
Repeatedly increasing down pointer 4 times and repeatedly decreasing up ointer 3 times I have 33,48,37,25,92,86,57

Then down=4,up=3.
Interchange x[up] with x[lb]
I have 25,48,37,33,92,86,57 j=up=3.

But clearly this is not partitioned correctly around 57.

I can't see what mistake I am making.Therefore if someone can help me to figure out this mistake that would be really helpful

Answer 1

after interchanging x[down] with x[up] you have to update down and up too. step 3 should be modified as: Step 3: if up > down then interchange x[down] with x[up] and down++ and up--. The process is repeated until the condition in step 3 fails ( i.e up =< down) at that point x[up] is interchanged with x[lb] ( which equal to a), whose final position was sought and j(i.e final position) is set to up.