Question

Assume the following list of keys: 36,55,89,95,65,75,13,62,86,9,23,74,2,100,98 This list is to be sorted using the quick sort algorithm as discussed in this chapter. Use pivot as the middle element of the list. a. Give the resulting list after one call to the function partition. b. What is the size of the list that the function partition partitioned? c. What are the sizes of the two sublists created by the function partition?

Short answer

a. [36, 55, 13, 9, 23, 2, 62, 89, 95, 65, 75, 86, 74, 100, 98] b. 15 elements c. Left: 6 elements, Right: 8 elements.

Step-by-step solution

Determine the Pivot

To perform the quick sort, we identify the pivot element of the list. In quicksort, the pivot is typically chosen from the list of numbers. In this case, the pivot is given as the middle element of the list. So first, we calculate the middle index of the list The list: \([36, 55, 89, 95, 65, 75, 13, 62, 86, 9, 23, 74, 2, 100, 98]\) The number of elements in the list is 15, so the middle element is the 8th element (0-based index), which is 62.

Rearrange Elements around the Pivot

Once the pivot (62) is chosen, partition the list such that all elements less than or equal to the pivot go to the left, and all elements greater go to the right.Starting from the beginning of the list: - Elements less than 62: \([36, 55, 13, 9, 23, 2]\)- Pivot: \(62\)- Elements greater than 62: \([89, 95, 65, 75, 86, 74, 100, 98]\)Combine them in the order: \([36, 55, 13, 9, 23, 2, 62, 89, 95, 65, 75, 86, 74, 100, 98]\).

Count Elements in the List Partitioned

The partition function is applied to the entire list whose size is the total number of elements. Count the elements in the current list: \(n = 15\). Thus, the entire list of 15 elements is the size for this partitioning step.

Determine the Sizes of the Two Sublists

After partitioning the list around the pivot (62), two sublists are formed.- The left sublist has elements: \([36, 55, 13, 9, 23, 2]\).- The right sublist has elements: \([89, 95, 65, 75, 86, 74, 100, 98]\).Count the elements in each sublist:- Size of left sublist: \(6\)- Size of right sublist: \(8\)

Key concepts

Pivot Selection

Choosing the right pivot is a crucial part of the Quicksort algorithm because it significantly impacts the efficiency of the sorting process. Different strategies exist for selecting a pivot, such as selecting the first element, the last element, or using a random element. However, in our case, we are choosing the middle element as the pivot.

To determine the pivot when sorting our list

• 36, 55, 89, 95, 65, 75, 13, 62, 86, 9, 23, 74, 2, 100, 98

we first compute the middle index. Since there are 15 elements, the middle one (0-based index) is at the 7th position, which is 62. This element becomes our pivot. This choice helps to somewhat balance the resulting sublists, minimizing the worst-case time complexity of the algorithm.

List Partitioning

List partitioning is a process of rearranging elements in the list with respect to the chosen pivot. The goal is to move all elements less than or equal to the pivot to its left, and all greater elements to its right.

In our example, after identifying 62 as the pivot, we start partitioning:

• Scan from left; gather elements less than or equal to 62: 36, 55, 13, 9, 23, 2
• Keep 62 as the pivot in the center
• Place elements greater than 62 on the right: 89, 95, 65, 75, 86, 74, 100, 98

The rearranged list becomes: 36, 55, 13, 9, 23, 2, 62, 89, 95, 65, 75, 86, 74, 100, 98. This partitioning sets the stage for further recursive sorting.

Sublists in Quicksort

After partitioning, Quicksort creates two sublists (or partitions) which will each undergo the Quicksort process independently. The strategy relies on the fact that these sublists are closer to sorted after the partitioning step.

In our example, we have:

• Left sublist: 36, 55, 13, 9, 23, 2
• Right sublist: 89, 95, 65, 75, 86, 74, 100, 98

The left sublist contains elements less than or equal to 62 and has a length of 6. The right sublist has elements greater than 62 and consists of 8 elements.

These sublists are then individually quicksorted, allowing the same process of pivot selection and partitioning to continue until each segment of the list is sorted.

Algorithm Steps

The Quicksort algorithm follows a systematic series of steps to sort the input list efficiently. Let’s break down these steps again for clarity:

• Start with an unsorted list and choose the middle element as the pivot.
• Partition the list around the pivot, arranging elements into two groups: less than or equal to the pivot, and greater than the pivot.
• Recursively apply the Quicksort algorithm to the two resultant sublists until the entire list is sorted.

By understanding how each of these steps depends on the previous one, you can see how the algorithm efficiently sorts lists through repeated division and conquer strategies. Mastering these steps, along with considering edge cases like empty sublists, ensures you have a solid grasp of Quicksort.