Question 1:

Write another partition method to partition an array into left sublist and right sublist based on a pivot value in the quick sort algorithm. All values in the left sublist are less than the pivot value, and all values in the right sublist are greater than or equals the pivot value.

When doing partitioning, using a start variable referencing the beginning of the array, and last variable referencing the ending of the array. We will still use the middle element as pivot value. Scan the array from both directions. If A[start] < pivot value, move start 1 position right, otherwise stop. If A[last] > pivot value, move last 1 position left, otherwise stop. Then swap A[start] and A[last]. Repeat the same process until start is the same as last. Then swap the pivot value with A[start] to finish the partition.

For example:

35 20 18 46 28 58 73 15 56 87

pivot value: 28

first we swap 35 with 28

start: index 1

last: index 9

20 < 28, move start to index 2. 18 < 28move start to index 3. 46 > 28, start stays here. endOfLeftList = index 2

87 > 28, move last to index 8, 56 > 28, move last to index 7. 15 < 28, last stays here

swap 46 with 15, endOfLeftList = 3.

swap pivot value with A[endOfLeftList]

Question 2: Implement the quick sort using the partition method defined in question 1.

Question 3: Analyze the time efficiency for your quick sort algorithm and get the big O of the algorithm.