Shown below is the 'Partition Algorithm' we developed.

Question

public static void partition(int[ ] data, int pivot) {

int i=0, j=data.length-1;

int temp;

while(i<=j) {

while(data[i]<pivot) i++;

while(data[j]>pivot) j--;

if(i<=j) {

temp = data[i];

data[i] = data[j];

data[j] = temp;

i++;

j--;

}

}

}

If the following array goes through

this partition algorithm using '12' as

the pivot, predict how the array will

look like:

19 5 7 11 43 17 22 20 9 10

Answer 1

There is no 12 in the data set. So either

we need to select another pivot, or add

the 12 to the list. I have chosen the latter.

Here is the original array

19 5 7 11 43 17 22 20 9 10 12

Pass one:

swaps 10 and 19

swaps 9 and 43

swaps 12 and 17

10 5 7 11 9 12 22 20 43 19 17 <-- items less than 12 are on it's left

items greater than 12 are on it's right

{10 5 7 11 9 }12 22 20 43 19 17 <-- 'left sub array pivot = 7

7 5 10 11 9 12 22 20 43 19 17 <--swaps 7 and 10

{7 5} 10 11 9 12 22 20 43 19 17 <-- ' left sub array pivot = 5

5 7 10 11 9 12 22 20 43 19 17 <-- swaps 5 and 7

5 7 {10 11 9 }12 22 20 43 19 17 <-- right sub array pivot = 11

5 7 10 9 11 12 22 20 43 19 17 <-- swaps 9 and 11

5 7 {10 9} 11 12 22 20 43 19 17 <-- right sub array, pivot =9

5 7 9 10 11 12{ 22 20 43 19 17} <-- right sub array, pivot = 43

5 7 9 10 11 12 22 20 17 19 43 <--- swaps 43 and 17

5 7 9 10 11 12 {22 20 17 19} 43 <-- sub array, pivot = 20

5 7 9 10 11 12 19 20 17 22 43 <-- swaps 19 and 22

5 7 9 10 11 12 {19 20 17} 22 43 <-- sub array pivot = 20

5 7 9 10 11 12 19 17 20 22 43 <--- swaps 17 and 20

5 7 9 10 11 12 {19 17} 20 22 43 <--- final sub array

sorting complete