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

Repeatedly increase the pointer down by one position until x[down] >= a - that should be > - after this you want to point at 57, which is greater than the pivot and should be swapped with an element that is smaller from the right-hand side of the array. — 500 - Internal Server Error
– 500 - Internal Server Error, Commented Jun 26, 2014 at 12:29
@500-InternalServerError : So the error is in the algorithm right? — clarkson
– clarkson, Commented Jun 26, 2014 at 13:24
Yes, it basically goes like this: Increase the left-hand index for as long as the value it points at is less or equal than the pivot. Then decrease the right-hand index for as long as the value there is greater than or equal to the pivot value. If the indexes haven't met, swap the two values, increase/decrease the indexes, and repeat. — 500 - Internal Server Error
– 500 - Internal Server Error, Commented Jun 26, 2014 at 13:29
@500-InternalServerError does equality come in both less or ewual and greater or equal?This algorithm works fine if x[down]>a and x[up]<=a — clarkson
– clarkson, Commented Jun 26, 2014 at 13:36

s.u.m.i.t · Accepted Answer · 2014-06-27 08:57:36Z

2

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.

answered Jun 27, 2014 at 8:57

s.u.m.i.t

513 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Quick sort partitioning algorithm.How it works

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related