Question

Assume the following list of keys:

78, 40, 16, 82, 64, 67, 57, 40, 37, 47, 72, 14, 17, 27, 55

This list is to be sorted using the quick sort algorithm as discussed in this chapter. Use pivot as the median of the first, last, and middle elements of the list.

1. What is the pivot?
2. Give the resulting list after one call to the partition function.

Answer 1

According to the problem statement,

The answers are as follows,

a) What is the pivot?

Answer: 55

Explanation:

• According to the rules of QuickSort, a pivot element can be the first element or can be a middle element or it can be last element or any random element from the array.
• But as a standard practise, most of the people will take last element of the array as PIVOT
• So, the pivot element is 55
• As you said first and last and middle elements, the pivot's are first = 78, middle = 40, last = 55

b) Give the resulting list after one call to the partition function?

Answer: 40, 16, 40, 37, 47, 14, 17, 27, 55, 64, 72, 67, 57, 78, 82

Explanation:

• According to the QuickSort rules, partition function will take arr, low and high elements as the parameters.
• low is the starting index of array 0
• high is the index of length-1        n-1
• After one call to the partition, the result will be like and the pivot 55 will gets its original place after whole sort.

I hope the above information and explanation will help you out!

Please comment if you have any queries/errors!

Thank you!