16.1.2. Partitioning and Efficiency

We have seen Quicksort which is a divide and conquer algorithm which overcomes the requirement for an extra array as in merge sort. So, let us do an analysis of Quicksort.

Remember how Quicksort works, you pick up a pivot element say typically this first element of an array. And then what you do is, you partition this into two parts such that you have a lower part which is less than or equal to p and may be have an upper part, this is bigger than p. And you move this pivot in between and then you sort this lower part and upper part separately recursively and then you do not need to do any combining step, because these two things are within the correct position with respect to each other.

Quicksort is a sorting algorithm that utilizes the divide-and-conquer approach, meaning it breaks down a problem into smaller sub-problems to solve them efficiently. The process begins by selecting a 'pivot' element from the array. The array is then divided into two segments: one containing elements less than or equal to the pivot, and the other containing elements greater than the pivot. After partitioning, the pivot is placed in its correct position, and both segments are sorted recursively. This allows the final sorted array to be assembled without needing an additional merging step, which is typically required in algorithms like Merge Sort.

Imagine organizing a stack of cards. You pick one card as a ‘pivot’ and lay it down. Next, you separate all cards lower than that pivot down to one side, and all higher cards to another side. After each separation, you continue organizing each side using the same method, without needing a secondary stack, just like in Quicksort. This method is efficient because each time you partition, you get closer to a fully organized deck.

So, the first thing we observed is that this partitioning actually is quite efficient. We can do it in one scan of the entire array. So, we can partition with respect to any pivot in order n time.

The partitioning step of Quicksort is efficient because it only requires a single pass (or scan) through the array. During this scan, the algorithm compares each element to the pivot and places it in the appropriate segment—either less than or greater than the pivot. This efficiency is significant because it means that no matter the size of the array, this partitioning process will only take linear time, i.e., O(n).

Think of filling two boxes with a set of different LEGO bricks. If you take each brick one-by-one and decide which box to put it in—depending on its color—you're performing a single scan of all the bricks. After going through all the bricks once, each box will be filled only with the corresponding bricks. This straightforward method is efficient, similar to the way Quicksort partitions an array in linear time.

If the pivot is a median then you would expect that by definition in median that these are of size n by 2. Because, the median is that element which splits the array into two parts, those half of the elements are bigger than the median, half are smaller than the median.

In the best-case scenario for Quicksort, the pivot chosen is the median value of the array. This means that when the array is partitioned, both segments created will be approximately equal in size (about n/2). This leads to a balanced recursive division, where the algorithm exhibits its most efficient performance. Such a situation results in a time complexity of O(n log n) because the algorithm will need to perform O(log n) levels of recursion while maintaining a linear time complexity for each level.

Imagine sorting a group of students by height. If you choose to measure the height of the student in the middle of the line as a pivot, you will likely have an equal number of students shorter and taller than that one. This optimal choice (the median) leads to a smooth and balanced sorting process, much like how the algorithm performs efficiently in its best case.

What do we think is a worst case? When the worst case is when the pivot is an extreme value, either the smallest value or the biggest value. So, if it is a smallest value then what will happen is that everything will be bigger than the pivot.

The worst-case scenario for Quicksort occurs when the pivot chosen is either the smallest or largest element in the array. In such cases, one of the segments created is empty, leading to highly unbalanced partitions during recursive calls. For example, if the pivot is the smallest value, all other elements will be placed in the upper segment, which leads to inefficient sorting. This results in a time complexity of O(n²), similar to other simpler quadratic sorting algorithms such as selection sort and insertion sort.

Consider organizing a queue. If the first person in line is the shortest and you choose them as your pivot, everyone else (being taller) will keep getting added to the line without any grouping around the shortest. Thus, every person must be reviewed individually while sorting, creating a very long process. This is akin to Quicksort's worst-case performance - disorganized and time-consuming.

So, it turns out that Quicksort we can show actually does not behave in this worst case way in a very frequent manner. So, we can actually compute in the case of Quicksort what is called the average case complexity and show that this n log n.

Despite the worst-case scenario for Quicksort resulting in O(n²) time complexity, it is important to note that these scenarios are rare in practice. The average-case complexity, which accounts for all potential input arrangements, actually results in O(n log n). This is calculated based on the fact that there are n! possible arrangements of inputs and by averaging the time taken across these, we can demonstrate the typical performance is significantly better than the worst case.

Imagine you frequently need to sort groups of colored marbles that can be arranged in numerous ways. While sometimes you may get a troublesome arrangement that takes longer to sort, most of the time, when you use a systematic approach (like Quicksort), sorting takes a reasonable amount of time. Over many sorting sessions, you notice that your average sorting time is quite efficient.

The solution is to not fix the strategy, each time I want to apply Quicksort to a recursive sub problem, I have some position 0 to n minus 1 which I need to pick as a pivot.

One way to avoid consistently choosing poor pivots, particularly in arrays that might lead to worst-case scenarios, is by implementing a randomization technique for selecting the pivot. Instead of always choosing the first element, one can randomly choose any index from the available range. This randomization helps in obtaining a better 'expected' running time of O(n log n) because it diminishes the likelihood of encountering the worst-case input consistently.

Think of rolling a die to pick a student for a presentation out of a group. If you blindly choose the first student every time, you might consistently get the same one, leading to an unbalanced distribution. However, if you roll a die to select any student randomly, every student has a fair chance, leading to a more balanced and varied presentation order.

--