Illustrating the PARTITION Operation

The initial values of the variables used in the PARTION operation are listed below.

The total number of elements in the array is 12.

The specified array A is

p = 0

r = 11

Now, the initial array with the initial positions:

In the PARTION operation,

The pivot element

The variable,

And another variable,

And the variable j is not more than r – 1, that is

Now, the array with the new positions:

The condition is failed, since and x = 11.

So, there will be no changes in the array.

The variable j is incremented by one, therefore, j = 1

And the variable j is not more than r – 1, that is

And no changes are made in other variables.

Now, the array with the new positions:

The condition is failed, since and x = 11.

So, there will be no changes in the array.

The variable j is incremented by one, therefore, j = 2

And the variable j is not more than r – 1, that is

And no changes are made in other variables.

Now, the array with the new positions:

The elements in the heavily shaded array are greater than x.

The condition is successful, since and x = 11.

So, the variable i is incremented by one, therefore, i = 0

And the value at the position i is swapped with the value at the position j.

That is, the values and are exchanged with each other.

Now, the array is:

The variable j is incremented by one, therefore, j = 3

And the variable j is not more than r – 1, that is

Now, the array with the new positions:

The elements in the heavily shaded array are greater than x.

The elements in the lightly shaded array are not greater than x.

The condition is successful, since and x = 11.

So, the variable i is incremented by one, therefore, i = 1

And the value at the position i is swapped with the value at the position j.

That is, the values and are exchanged with each other.

Now, the array is:

The variable j is incremented by one, therefore, j = 4

And the variable j is not more than r – 1, that is

Now, the array with the new positions:

The elements in the heavily shaded array are greater than x.

The elements in the lightly shaded array are not greater than x.

The condition is failed, since and x = 11.

So, there will be no changes in the array.

The variable j is incremented by one, therefore, j = 5

And the variable j is not more than r – 1, that is

Now, the array with the new positions:

The elements in the heavily shaded array are greater than x.

The elements in the lightly shaded array are not greater than x.

The condition is successful, since and x = 11.

So, the variable i is incremented by one, therefore, i = 2

And the value at the position i is swapped with the value at the position j.

That is, the values and are exchanged with each other.

Now, the array is:

The variable j is incremented by one, therefore, j = 6

And the variable j is not more than r – 1, that is

Now, the array with the new positions:

The elements in the heavily shaded array are greater than x.

The elements in the lightly shaded array are not greater than x.

The condition is successful, since and x = 11.

So, the variable i is incremented by one, therefore, i = 3

And the value at the position i is swapped with the value at the position j.

That is, the values and are exchanged with each other.

Now, the array is:

The variable j is incremented by one, therefore, j = 7

And the variable j is not more than r – 1, that is

Now, the array with the new positions:

The elements in the heavily shaded array are greater than x.

The elements in the lightly shaded array are not greater than x.

The condition is successful, since and x = 11.

So, the variable i is incremented by one, therefore, i = 4

And the value at the position i is swapped with the value at the position j.

That is, the values and are exchanged with each other.

Now, the array is:

The variable j is incremented by one, therefore, j = 8

And the variable j is not more than r – 1, that is

Now, the array with the new positions:

The elements in the heavily shaded array are greater than x.

The elements in the lightly shaded array are not greater than x.

The condition is failed, since and x = 11.

So, there will be no changes in the array.

The variable j is incremented by one, therefore, j = 9

And the variable j is not more than r – 1, that is

Now, the array with the new positions:

The elements in the heavily shaded array are greater than x.

The elements in the lightly shaded array are not greater than x.

The condition is successful, since and x = 11.

So, the variable i is incremented by one, therefore, i = 5

And the value at the position i is swapped with the value at the position j.

That is, the values and are exchanged with each other.

Now, the array is:

The variable j is incremented by one, therefore, j = 10

And the variable j is not more than r – 1, that is

Now, the array with the new positions:

The elements in the heavily shaded array are greater than x.

The elements in the lightly shaded array are not greater than x.

The condition is successful, since and x = 11.

So, the variable i is incremented by one, therefore, i = 6

And the value at the position i is swapped with the value at the position j.

That is, the values and are exchanged with each other.

Now, the array is:

The variable j is incremented by one, therefore, j = 11

But, the variable j is more than r – 1, that is , since r = 11

Now, the array with the new positions:

The elements in the heavily shaded array are greater than x.

The elements in the lightly shaded array are not greater than x.

Since the variable j is more than r – 1, that is , since r = 11

So, the loop will be terminated.

And the value at the position i + 1 is swapped with the value at the position r.

That is, the values and are exchanged with each other.

The element in the not shaded array is the pivot element.

And the PARTION procedure returns the position of the pivot element.

Therefore, here, the procedure returns 7.

Hence, the array after the first call of the PARTION procedure:

Similarly, the array after the second call of the PARTION procedure:

The array after the third call of the PARTION procedure:

The array after the fourth call of the PARTION procedure:

The array after the fifth call of the PARTION procedure:

The array after the sixth call of the PARTION procedure:

The array after the seventh call of the PARTION procedure:

The array after the eighth call of the PARTION procedure:

The array after the last call of the PARTION procedure:

For this array the PARTION procedure is called 9 times to sort the elements in the array in the non-descending order.

When all the elements in the array A[p..r] have the same value, the PARTITION algorithm returns r as the value of q.

• In the for loop, Line 4 checks whether .When all the elements in A are same, the comparison is always satisfied, and hence, i is incremented in each iteration.

• When the for loop terminates, the value of i will be equal to r-1.

• In line 8, the value of i is again incremented by 1, and is returned.

Hence, r is returned to q by the PARTITION algorithm when all the elements in the array A[p..r] have the same value.

The modified version of the PARTITION algorithm, such that it returns when all the elements in the array A[p..r] have the same value, is as follows:

Modified- PARTITION (A, p, r)

// Assign the last element of the subarray to x

1. x= A [r]

// Initialize i and k to p-1

2. i = p – 1

3. k = p – 1

// repeat the loop for j from p to r-1

4. for j = p to r – 1

// check whether A [j] is greater than x. If true, increment the value of k and i.

5. if A [j] <

6. k =k + 1

7. exchange A [j] A [k]

8. i = i + 1

// check whether A [j] is equal to x. If true, increment the value of i.

9. if A [j]=

10. i = i + 1

11. exchange A [i] A [j]

12. exchange A [i+1] A [R]

13. return

In the PARTITION procedure, A is an array of n elements, p is the first index in the array, and r is the last index in the array.

• The variable i moves from left to right, and the variable j moves from right to left in the array. That is, variable j moves from the 2^nd element to the last element, and variable i moves till j, comparing each element. Hence, there are n comparisons.

• The total number of moves of i and j in the for loop is n, where n is the total number of elements in the array, that is, .

• Therefore, every repetition of the for loop includes a constant number of operations. Thus, the running time of this step is.

• The running time of each increment of variable i is constant.

• The running time of each increment of variable j is constant.

• The running time of each exchange of elements is constant.

Hence, the running time of the PARTITION procedure on a sub-array with n elements is .