Question 2

Consider the quick-sort algorithm we discussed in the class. One important component of the quick-sort algorithm is partition. A pseudocode of the partition is shown below:

partition(int[] a, int x, int y) { left = x; right = y-1; z = a[y]; while (left <= right) { while (left <= right AND a[left] < z) increment left; while (left <= right AND a[right]> z) decrement right; if (left <= right) { swap a[left] with a[right]; increment left; decrement right; } } swap a[left] with a[y]; }

Here, we assume that

• The array to be partitioned is an array of integers
• All variables are appropriately declared
• Initial call is made with partition(a, 0, a.length-1)

Suppose you invoke the above partition algorithm with: partition(a, 0, a.length-1), where

a = {42, 10, 17, 45, 57, 31, 9, 5, 31, 29}

Which of the following is the content of the array a after the partition has been executed? Choose one.

	a.	{5, 10, 17, 9, 29, 57, 31, 45, 42, 31}
	b.	{10, 17, 9, 5, 29, 42, 45, 57, 31, 31}
	c.	{5, 10, 17, 9, 29, 31, 45, 42, 31, 57}
	d.	{5, 9, 10, 17, 29, 31, 31, 42, 45, 57}