Question

(Quicksort) The recursive sorting technique called quicksort uses the following basic algorithm for a one-dimensional vector of values: a. Partitioning Step : Take the first element of the unsorted vector and determine its final location in the sorted vector (i.e., all values to the left of the element in the vector are less than the element, and all values to the right of the element in the vector are greater than the elementwe show how to do this below). We now have one element in its proper location and two unsorted subvectors. b. Recursion Step : Perform Step 1 on each unsorted subvector. Each time Step 1 is performed on a subvector, another element is placed in its final location of the sorted vector, and two unsorted subvectors are created. When a subvector consists of one element, that element is in its final location (because a one-element vector is already sorted). The basic algorithm seems simple enough, but how do we determine the final position of the first element of each subvector? As an example, consider the following set of values (the element in bold is the partitioning elementit will be placed in its final location in the sorted vector): $$\begin{array}{llllllllll} 37 & 2 & 6 & 4 & 89 & 8 & 10 & 12 & 68 & 45 \end{array}$$

Short answer

First, choose the element as the pivot, rearrange around it, then recursively sort the sub-lists.

Step-by-step solution

Choose the Pivot

For the partitioning step, we take the first element as the pivot. In this case, the pivot is 37.

Rearrange Elements

Rearrange the vector such that all elements less than 37 are moved to its left, and all elements greater or equal to 37 are moved to its right. The temporary rearrangement looks like \[\begin{array}{llllllllll} 2 & 6 & 4 & 8 & 10 & 12 & 37 & 89 & 68 & 45 \end{array}\].

Place Pivot in Final Position

Place the pivot (37) in its correct final position within the rearranged vector. At this point, 37 is placed between the two groups: \[\begin{array}{llllllllll} 2 & 6 & 4 & 8 & 10 & 12 & 37 & 89 & 68 & 45 \end{array}\].

Partition Left Subvector

Take the left subvector \([2, 6, 4, 8, 10, 12]\) and perform the partition step again with 2 as the new pivot. After rearranging, the vector becomes \[\begin{array}{llllll} 2 & 6 & 4 & 8 & 10 & 12 \end{array}\], since all elements are already greater than 2.

Partition Right Subvector

Now focus on the right subvector \([89, 68, 45]\). Choose 89 as the pivot. Rearrange to make sure elements less than 89 are to its left: \[\begin{array}{lll} 68 & 45 & 89 \end{array}\].

Continue Recursion on Sublists

For the left of the pivot 2, nothing needs to be done since it's a single element. Therefore, proceed to sort the sublists \([6, 4, 8, 10, 12]\) and \([68, 45]\) recursively using the previous steps.

Final Checks and Completion

Repeat Steps 4 to 6 until each element is checked and placed in its final position. Sub-vectors break down further until each element stands alone, signalling the end of the sort.

Key concepts

Recursive Sorting

Recursive sorting is a fundamental concept at the heart of the quicksort algorithm. What makes quicksort powerful is its ability to break a larger problem into smaller, more manageable parts through the process of recursion. In quicksort, recursion begins with the entire unsorted vector. The vector is divided until it cannot be divided further. This recursive approach simplifies complex sorting tasks.

1. **Division into Subvectors**: Initially, the vector is partitioned into two subvectors, usually around a pivot element (more about this in the next section).
2. **Recursive Calls**: The algorithm then calls itself to sort each of these subvectors. As the recursion proceeds, each subvector divides further into smaller parts.
3. **Base Case**: The recursion stops when a subvector has only one element. Here, quicksort recognizes it as sorted.

This procedure efficiently organizes data, starting from smaller tasks and combining them to solve the larger problem.

Pivot Selection

Pivot selection is a crucial step in the quicksort algorithm. The pivot is the central element around which the vector is partitioned. The choice of pivot can significantly influence the efficiency of the sort.

Here are some key points about pivot selection:

• **Simple Selection**: In the basic version of quicksort, the first element of the vector is chosen as the pivot, as demonstrated in the exercise.
• **Alternative Choices**: More advanced techniques involve choosing a random element, the last element, or even the median of the vector to reduce the chances of poor performance.
• **Impact on Performance**: An ideal pivot evenly splits the vector, leading to balanced recursion and optimized performance.

The selection must handle all eventualities, ensuring that the sorting continues effectively, minimizing time complexity.

Partitioning Algorithm

The partitioning algorithm in quicksort is where the action happens. It's the step where the selected pivot is used to divide the vector into two parts.

Here's how it works:

• **Rearrangement**: The algorithm rearranges elements such that those less than the pivot move to its left, and those greater move to its right, creating two new subvectors.
• **Placement**: Once rearranged, the pivot is placed between these two groups. This step ensures that it's in the correct final position.
• **Subvector Creation**: The vector is now divided into two unsorted subvectors to be processed in further recursive steps.

This partitioning efficiently isolates elements around the pivot, ensuring continuous progress of the sorting process.

Vector Sorting

Vector sorting with quicksort involves organizing a collection of numbers or elements stored in a one-dimensional vector. This method uses the principles of recursive sorting, pivot selection, and partitioning to achieve a fully sorted vector.

Here's a quick breakdown:

• **Initial Arrangement**: Begin with a one-dimensional vector, unsorted.
• **Recursive Sorting Methodology**: Use the recursive quicksort technique to continuously break down the vector into smaller parts.
• **Arrange and Finalize**: Through continuous partitioning and recursive calls, each element reaches its final sorted position.
  The vector sorting completes when all elements are correctly organized, resulting in a sorted sequence from smallest to largest.

This systematic approach ensures that the sorting is done efficiently, making quicksort a popular choice for sorting data structures.