Problem

(i) A list of twelve numbers is to be sorted into ascending order.

$28 \quad 18 \quad 50 \quad 27 \quad 48 \quad 8 \quad 25 \quad 12 \quad 56 \quad 31 \quad 33 \quad 42$

(a) Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.

(b) Show how the binary search algorithm is used to try to locate the number 40 in the list. You must clearly indicate your choice of pivots and which part of the list you are rejecting.

(ii) A different list of nine distinct integers is to be sorted into descending order.

$23 \quad 20 \quad x \quad 32 \quad 15 \quad 8 \quad 19 \quad 6 \quad 22$

The list is sorted using bubble sort. The first three passes are

Pass 1	23	20	32	x	15	19	8	22	6
Pass 2	23	32	20	x	19	15	22	8	6
Pass 3	32	23	20	19	x	22	15	8	6

Determine the range of possible values of $x$.