Question

1a)Use the Lomuto's quicksort algorithm to sort the following list of integers in nondecreasing order for the first pivot item. Use pointers i and j for swapping items (if necessary) for each step leading to your answer. Note do the problem just for the first pivot item.

123,34,189,56,150,12,9,24

1b)Use the same list of numbers and use the Hoare's quicksort algorithm using pointers l and r and updating the pointers i and j and swapping items. Do the problem just for the first pivot item.

123,34,189,56,150,12,9,24

Answer 1

(1a) Use Lomuto's quicksort algorithm to sort the following list of integers in non decreasing order ( i.e. increasing order) for first pivot item only.

The elements are as shown below:

123, 34, 189, 56, 150, 12, 9, 24

Solution:

Let's assume that above elements are stored in array A[ ]. First element is stored at index 0.

We use two pointers: low and high

Where low points to the first element (at index 0) of the array A.

and high points to the last element of the array A.

In our example, low = 0 and high = 7

We use two more pointers for swapping items for each step: i and j

Initially i = 0 and j = 0

In Lomuto's quicksort algorithm we use last element as pivot element.

so, pivot = a[high] = 24

Before solving example step by step, let's usderstand the steps that we need to follow.

We process all the elements using variable j as follows:

For j = low to high-1 do

if ( A[ j ] < pivot) then

swap ( A[ i ] , A[ j ] )

i = i + 1

done \\ for loop is over

swap ( A[ i ] , A [ high ] )

Step-1:

123, 34, 189, 56, 150, 12, 9, 24

i = 0, j = 0

check A [ 0 ] < pivot, i.e. 123 < 24 : No.

So, increament value of j (j = j + 1) and move to next step.

Step-2:

123, 34, 189, 56, 150, 12, 9, 24

i = 0, j = 1

check A [ 1 ] < pivot, i.e. 34 < 24 : No.

So, increament value of j (j = j + 1) and move to next step.

Step-3:

123, 34, 189, 56, 150, 12, 9, 24

i = 0, j = 2

check A [ 2 ] < pivot, i.e. 189 < 24 : No.

So, increament value of j (j = j + 1) and move to next step.

Step-4:

123, 34, 189, 56, 150, 12, 9, 24

i = 0, j = 3

check A [ 3 ] < pivot, i.e. 56 < 24 : No.

So, increament value of j (j = j + 1) and move to next step.

Step-5:

123, 34, 189, 56, 150, 12, 9, 24

i = 0, j = 4

check A [ 4 ] < pivot, i.e. 150 < 24 : No.

So, increament value of j (j = j + 1) and move to next step.

Step-6:

123, 34, 189, 56, 150, 12, 9, 24

i = 0, j = 5

check A [ 5 ] < pivot, i.e. 12 < 24 : Yes.

Swap ( A[ 0 ] , A [ 5 ] ), means swap 123 and 12.

So the array after swapping is: 12, 34, 189, 56, 150, 123, 9, 24

i = i + 1 = 0 + 1 = 1

Increament value of j (j = j + 1) and move to next step.

Step-7:

12, 34, 189, 56, 150, 123, 9, 24

i = 1, j = 6

check A [ 6 ] < pivot, i.e. 9 < 24 : Yes.

Swap ( A[ 1 ] , A [ 6 ] ), means swap 34 and 9.

So the array after swapping is: 12, 9, 189, 56, 150, 123, 34, 24

i = i + 1 = 1 + 1 = 2

Increament value of j (j = j + 1) and move to next step.

Now value of j = 7 so we terminate the loop.

Step-8:

i = 2, high = 7

swap ( A[ i ] , A [ high ] )

swap ( A [ 2 ], A [ 7 ] ) , means swap 189 and 24.

So the array after swapping is: 12, 9, 24, 56, 150, 123, 34, 189

This is the end of explanation for the first pivot item.

You can see from the final output that values less than pivot (24) is on the left hand side and values greater than pivot is on the right side of the pivot element (24).

(1b) Use Hoare's quicksort algorithm to sort the following list of integers in non decreasing order ( i.e. increasing order) for first pivot item only.

The elements are as shown below:

123, 34, 189, 56, 150, 12, 9, 24

Solution:

Let's assume that above elements are stored in array A[ ]. First element is stored at index 0.

We use two pointers: low and high

Where low points to the first element (at index 0) of the array A.

and high points to the last element of the array A.

In our example, low = 0 and high = 7

We use two more pointers for swapping items for each step: l and r

Initially l = low and r = high-1, so l = 0 and r = 6

Let's use last element as pivot element.

so, pivot = a[high] = 24

Before solving example step by step, let's usderstand the steps that we need to follow.

We process all the elements using variable j as follows:

Step-1: Select the bigger element than the pivot by searching forward from the left side (lower bound) of the array

i.e. While ( A [ l ] <= pivot )

l = l + 1;

Step-2: Select the smaller element than the pivot by searching backward from the right side (upper end) of the array.

i.e. While ( A [ r ] >= pivot )

r = r - 1;

Step-3: Swap ( A [ l ] , A [ r ] )

Step-4: Repeat above steps until they detect inversion (i.e. l and r cross each other)

i.e. Stop excuting above steps (1 to 3) when l > r.

Step-5: Swap ( A [ l ] , pivot )

Let's see step by step illustration of the example:

Step-1:

123, 34, 189, 56, 150, 12, 9, 24

l = 0 and r = 6

If A [ 0] < = pivot, 123 < =24 : No.

If A [ 6] > = pivot, 9 >= 24 : No.

Swap ( A [0] , A [ 6 ])

So the array after swapping is: 9. 34, 189, 56, 150, 12, 123, 24

Step-2:

9. 34, 189, 56, 150, 12, 123, 24

l = 1 and r = 5

If A [ 1] < = pivot, 34 < =24 : No.

If A [ 5] > = pivot, 12 >= 24 : No.

Swap ( A [1] , A [ 5 ])

So the array after swapping is: 9. 12, 189, 56, 150, 34, 123, 24

Step-3:

9. 12, 189, 56, 150, 34, 123, 24

l = 2 and r = 4

If A [ 2] < = pivot, 189 < =24 : No.

If A [ 4] > = pivot, 150 >= 24 : Yes. decrement value of r.

If A [ 3] > = pivot, 56 >= 24 : Yes. decrement value of r.

If A [ 2] > = pivot, 189 >= 24 : Yes. decrement value of r.

Now l = 2 and r = 1 so they cross each other. Stop the loop.

Step-4:

Swap ( A[ 2] , A [7] )

So the array after swapping is: 9, 12, 24, 56, 150, 34, 123, 189

This is the end of explanation for the first pivot item.

You can see from the final output that values less than pivot (24) is on the left hand side and values greater than pivot is on the right side of the pivot element (24).