So far, we have learned about implementing the Quicksort algorithm with the pivot element chosen as the first element or the middle element in the array. We have also discussed the significance of the pivot's position.
However, you might still be wondering, where are divide, conquer and combine steps in this implementation. Let's go through this:
The divide step occurs in the partition function, where the array is divided into two subarrays based on a chosen pivot element. The pivot element is selected from the array, and the partition function rearranges the elements such that all elements smaller than the pivot are on the left side, and all elements greater than the pivot are on the right side. This partitioning step essentially divides the array into two subarrays.
The conquer step is the recursive part of the algorithm, implemented in the quickSort function. After dividing the array into subarrays, the quickSort function is called recursively on each subarray. This recursive call applies the same divide-and-conquer process to the subarrays, further dividing them into smaller subarrays until the base case is reached.
In the Quicksort algorithm, there is no explicit combine step. Instead, the combine step is implicitly handled during the partitioning process in the partition function. As the partition function partitions the array and places the pivot element at its correct sorted position, it effectively combines the sorted subarrays. This process does not significantly affect the overall time complexity.
In the next assignment, we will provide a more detailed explanation of the time complexity of the Quicksort algorithm.