Question

Assume the following list of keys: 48,30,66,50,9,95,80,15,25,18,94,55,3,22,62 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. a. What is the pivot? b. Give the resulting list after one call to the function partition. c. What is the size of the list that the function partition partitioned? d. What are the sizes of the two sublists created by the function partition?

Short answer

a. Pivot is 62. b. Resulting list: 48,30,55,50,9,3,15,25,18,22,62,95,80,66,94. c. Partition size is 15. d. Sublists sizes are 10 and 4.

Step-by-step solution

Determine the Pivot

First, we need to find the pivot using the median-of-three rule involving the first, last, and middle elements of the list. The first element is 48, the last is 62, and the middle element is 95 (since the list length is 15, the middle index is \( \frac{15}{2} = 7 \), so the element at index 7 is 95). To find the pivot, we arrange these three numbers in order: 48, 62, and 95. The median of these is 62. Thus, the pivot for the partition function is 62.

Partition the List

To partition the list, arrange elements such that elements less than the pivot (62) are on the left and those greater are on the right. Start with the list: 48,30,66,50,9,95,80,15,25,18,94,55,3,22,62. After one partition around the pivot 62, the elements rearrange to 48,30,55,50,9,3,15,25,18,22,62,95,80,66,94, where elements left of 62 are less than or equal to 62 and those to the right are greater.

Size After Partition

After partitioning, the size of the function partitioned is the same as the original list, which is 15, because the partition does not change the number of elements, it only rearranges them according to the pivot.

Determine the Sizes of Sublists

The partition function creates two sublists. In this case, the left sublist includes elements {48,30,55,50,9,3,15,25,18,22}, which has a size of 10, and the right sublist includes {95,80,66,94}, which has a size of 4. The pivot itself is considered separate, making the counts match with the original list size of 15.

Key concepts

Pivot Selection

In the Quick Sort algorithm, selecting the right pivot is crucial for efficiency. The pivot is the element that helps in dividing the array into smaller segments for sorting. Using a poor pivot can degrade Quick Sort's performance dramatically. In this context, we use a "Median of Three" strategy to choose the pivot.

This strategy involves comparing three elements for selection:

• The first element of the list.
• The last element of the list.
• The middle element of the list.

We sort these three values and select the median value as the pivot. This helps mitigate the worst-case time complexity of Quick Sort by avoiding extremely unbalanced partitions. In our specific exercise:

• First element: 48
• Last element: 62
• Middle element: 95

Sorting these values gives 48, 62, and 95. The median is 62, so 62 becomes our pivot.

Median of Three

The "Median of Three" method is an enhancement to the classic Quick Sort algorithm. It is designed to improve Quick Sort’s average performance by providing more balanced partitions. By picking the median of three elements, this technique reduces the chance of selecting poor pivots, especially on partially sorted or patterned data.

The steps to implement the "Median of Three" are as follows:

• Identify the first, middle, and last elements of the array segment currently being sorted.
• Sort these three elements to find the median.
• Use this median as the pivot for partitioning the array.

For example, in a list of 15 elements, the middle element is at index 7 (as integer division of 15 by 2). Considering the indices, the elements evaluated were 48, 62, and 95. The median, 62, becomes the pivot for partitioning. This chosen pivot is less likely to be an extremely small or large value, leading to better partitioning.

Partitioning

Partitioning is a fundamental part of the Quick Sort algorithm. This process reorganizes the elements in relation to the pivot. During partitioning, elements smaller than the pivot are moved to its left, and those greater are moved to its right.

Using 62 as the pivot, the original list \[48, 30, 66, 50, 9, 95, 80, 15, 25, 18, 94, 55, 3, 22, 62\] is rearranged. In this exercise, the result is\[48, 30, 55, 50, 9, 3, 15, 25, 18, 22, 62, 95, 80, 66, 94\].

• Elements less than or equal to the pivot move to its left.
• Elements greater than the pivot move to its right.
• The pivot (62) itself is placed between these partitions.

After partitioning, the pivot is in its final sorted position, dividing the list into two sublists to be sorted recursively.

Divide and Conquer

Divide and Conquer is the strategy underpinning the Quick Sort algorithm. The whole process involves breaking down a problem into simpler sub-problems, solving each independently, and combining these solutions.

In Quick Sort, this strategy is applied by:

• Choosing a pivot element using methods like "Median of Three".
• Partitioning the array around this pivot.
• Recursively applying Quick Sort to the resulting sublists, excluding the pivot.

Here, after the pivot 62 was selected and the list partitioned, Quick Sort proceeds to sort the divided sublists \([48, 30, 55, 50, 9, 3, 15, 25, 18, 22]\) and \([95, 80, 66, 94]\). Each sublist undergoes the same process: selecting a pivot, partitioning, and further sorting until they are fully sorted. This method effectively reduces the problem size at each step, leading to efficient sorting.