Question

(Quicksort) You have previously seen the sorting techniques of the bucket sort and selection sort. We now present the recursive sorting technique called Quicksort. The basic algorithm for a single-subscripted array of values is as follows: a. Partitioning Step: Take the first element of the unsorted array and determine its final location in the sorted array (i.e., all values to the left of the element in the array are less than the element, and all values to the right of the element in the array are greater than the element). We now have one element in its proper location and two unsorted subarrays. b. Recursive Step: Perform Step 1 on each unsorted subarray. Each time Step 1 is performed on a subarray, another element is placed in its final location of the sorted array, and two unsorted subarrays are created. When a subarray consists of one element, that subarray must be sorted; therefore, that element is in its final location. The basic algorithm seems simple enough, but how do we determine the final position of the first element of each subarray? 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 array): 37 2 6 4 89 8 10 12 68 45 a. Starting from the rightmost element of the array, compare each element with 37 until an element less than 37 is found. Then swap 37 and that element. The first element less than 37 is 12, so 37 and 12 are swapped. The values now reside in the array as follows: 12 2 6 4 89 8 10 37 68 45 Starting from the left of the array, but beginning with the element after 12, compare each element with 37 until an element greater than 37 is found. Then swap 37 and that element. The first element greater than 37 is 89, so 37 and 89 are swapped. The values now reside in the array as follows: 12 2 6 4 37 8 10 89 68 45 Starting from the right, but beginning with the element before 89, compare each element with 37 until an element less than 37 is found. Then swap 37 and that element. The first element less than 37 is 10, so 37 and 10 are swapped. The values now reside in the array as follows: 12 2 6 4 10 8 37 89 68 45 Starting from the left, but beginning with the element after 10, compare each element with 37 until an element greater than 37 is found. Then swap 37 and that element. There are no more elements greater than 37, so when we compare 37 with itself, we know that 37 has been placed in its final location of the sorted array. Once the partition has been applied to the array, there are two unsorted subarrays. The subarray with values less than 37 contains 12, 2, 6, 4, 10 and 8. The subarray with values greater than 37 contains 89, 68 and 45. The sort continues with both subarrays being partitioned in the same manner as the original array. Based on the preceding discussion, write recursive function quickSort to sort a single subscripted integer array. The function should receive as arguments an integer array, a starting subscript and an ending subscript. Function partition should be called by quickSort to perform the partitioning step

Short answer

Use 37 as the pivot to partition the array, then recursively apply the same process to the resulting subarrays.

Step-by-step solution

Choose the Pivot

In QuickSort, the first element of the array is often chosen as the pivot. In the given array, the pivot is 37.

Partition the Array

The goal is to place 37 in its correct position with all smaller elements to the left and greater elements to the right. Start by moving from the right, find the first element smaller than 37, which is 12, and swap it with 37. The array becomes: 12 2 6 4 89 8 10 37 68 45.

Continue Partitioning from Left to Right

Now, move from the left (after 12) and find the first element larger than 37, which is 89, and swap it with 37. The array updates to: 12 2 6 4 37 8 10 89 68 45.

Swap Elements to Finalize Partition

Continuing from the right (before 89), find an element smaller than 37, which is 10, and swap it with 37, resulting in: 12 2 6 4 10 8 37 89 68 45.

Check for End of Partitioning

Move from the left (after 10) and continue until you are comparing 37 with itself. Since there are no elements greater than 37, it is in its final position.

Recursively Sort the Subarrays

Now, apply QuickSort recursively to the two subarrays: the left subarray (12 2 6 4 10 8) and the right subarray (89 68 45). Repeat the steps of choosing a pivot and partitioning until each subarray is sorted.

Implement Recursive Quicksort Function

The recursive function `quickSort` takes the array, starting subscript, and ending subscript as parameters. It uses the `partition` function to rearrange elements around a pivot, then recursively applies itself to the subarrays.

Key concepts

Recursive Algorithms

Quicksort is a prime example of a recursive algorithm, meaning it solves a problem by breaking it down into smaller, more manageable subproblems. This process continues until each subproblem is so straightforward that it can be solved directly. In the case of quicksort, this means sorting increasingly smaller subarrays.

Here's how the recursion in quicksort works: start by selecting a pivot element from the array and partition the rest of the array around that pivot. After placing the pivot in its correct position, quicksort takes the subarrays to the left and right of the pivot and applies the same process recursively. This division continues until subarrays consist of zero or one element, at which point they are inherently sorted. Thus, quicksort gradually builds up the sorted array by solving these smaller sorting challenges.

Key characteristics of recursive algorithms include:

• Base Case: a condition under which the recursion stops. For quicksort, this is when the subarray size is zero or one.
• Recursive Case: the part of the function that breaks the problem down. In quicksort, this involves partitioning the array around a pivot.

Recursion is a powerful tool because it breaks a complex problem (sorting an entire array) into much simpler subproblems (sorting smaller arrays), making the solution elegant and natural.

Array Partitioning

Array partitioning is at the heart of the quicksort algorithm. It's the process that positions the pivot element correctly so that all elements to its left are less, and all elements to its right are greater. After this, the pivot is in its final place, and the array is split into two unsorted subarrays.

To partition an array, start with the pivot (typically the first element). Move from the right end of the array toward the left to find an element smaller than the pivot, then swap it with the pivot. Next, move from the left side toward the right to find an element larger than the pivot and swap again. Continue alternating directions until the left and right pointers cross. At each step, swap elements so the pivot gradually moves toward the center.

The partitioning step ensures that each recursive call to quicksort works with subarrays that are closer to being sorted. It also guarantees that the pivot is in its correct sorted position in just one pass through the array, setting quicksort apart as a very efficient sorting technique, especially for large datasets.

This process describes how an array can be effectively divided and conquered, with elements being moved across the pivot with precision.

Sorting Techniques

Quicksort is one of the most popular sorting techniques due to its efficiency and simplicity. It employs a divide-and-conquer strategy to sort elements by leveraging both partitioning and recursion. This makes it very different from simpler algorithms like selection sort or bubble sort, which often require multiple passes through the entire dataset.

Quicksort works best with a good choice of pivot. Poor pivot selection can lead to decreased performance, especially in already sorted or nearly sorted data where it's comparable to the less efficient O(n²) algorithms. However, with a good pivot strategy, quicksort operates in O(n log n) time, making it very fast compared to other common sorting methods.

Its efficiency is particularly notable because quicksort sorts "in place," which means it requires minimal extra space, making it memory efficient. In practice, even though its average case is on par with other O(n log n) algorithms like mergesort, its cache performance and simplicity in implementation often give it an edge.

• Unlike bubble or selection sort, quicksort quickly reduces the size of the problem through partitioning.
• It handles large arrays efficiently, making it a preferred choice in many real-world applications.

Quicksort stands out for its balance between power and simplicity, making it a fundamental algorithm in computer science.