16.1.1. Introduction to Quicksort

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.

So, 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 uses a technique called divide and conquer. It starts by selecting a 'pivot' element within the array. The main steps are:

1. The array is divided into two parts: elements less than or equal to the pivot and those greater than the pivot.
2. The pivot is placed in its correct position, and then the algorithm sorts the two partitions independently.
3. No final merging step is needed because the elements are already sorted around the pivot. This is efficient because it reduces the complexity of sorting compared to other methods that may require additional space.

Imagine organizing a group of books on a shelf. You pick one book as your reference (the pivot). You then arrange all the books that are alphabetically before this book on one side, and all those that are after on the other side. Once the reference book is in its place, you can repeat this process with each side until all books are in order.

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 in Quicksort can be done in linear time, which means that its efficiency is quite high. In a single pass through the array of 'n' elements, we can compare each element to the pivot and place it in the correct partition. This characteristic is essential for the overall performance of the algorithm, contributing to its average-case efficiency.

Think of a magician who sorts out playing cards by choosing one card as the reference. The magician quickly spreads all other cards around this reference card based on whether they are higher or lower in rank. This sorting happens all at once, ensuring that the process is fast and efficient.

So, 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.

When the pivot chosen is the median, it effectively divides the array into two equal parts. This leads to an efficient sorting process because each recursive call processes smaller partitions of equal size. The case of choosing the median as the pivot results in the best-case time complexity of O(n log n) for Quicksort.

Imagine hosting a dinner where you split guests into two equal groups based on the age. If you select the median age for your split, you will have a balanced mix of older and younger guests in each group, making it easier to manage and organize activities.

What do we thing 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 arises when the pivot chosen is either the smallest or largest element. In this case, the algorithm repeatedly only partitions one side, leading to increasingly smaller sub-arrays. The time complexity in this case degrades to O(n^2), which is less efficient compared to the average case.

Consider a line of people organized by height who are taking turns to enter a building. If the shortest person is always selected to go first, everyone will line up behind them for their turn, effectively slowing down the entire entry process. This results in a longer wait time, similar to how poor pivot choices can slow down sorting.

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.

Although Quicksort has a worst-case time complexity of O(n^2), it often performs much better in practice. The average-case complexity, which accounts for all possible random inputs, turns out to be O(n log n). This is a result of the fact that most pivots will not be the extreme values, and thus the algorithm will effectively split the array into balanced parts most of the time.

Think about an average-sized group of people trying to line up alphabetically. Most of the time, they will be randomly arranged, which means they can organize themselves relatively quickly. However, in the rare case they start completely mixed up or in reverse order, it would take longer to sort out.

So, 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. But, rather than telling you that is going to be 0 or n minus 1 or the mid-way between 0 and n minus 1, I will say that I will choose any one of these values with equal probability.

To mitigate the worst-case scenario, a randomized version of Quicksort chooses the pivot element randomly from the array rather than following a fixed strategy. This not only helps avoid extreme values but also makes the sorting process more unpredictable, helping the algorithm perform efficiently across varying input states.

Imagine you are choosing a leader among friends for an activity. Instead of always selecting the tallest or the shortest person, you randomly select anyone from the group. This way, you reduce the chances of biases and ensure a more balanced selection process.

Now, it turns out in Quicksort you can actually manually make a recursive algorithm iterative. So, the point is that the recursive calls works on disjoint segments.

While Quicksort is typically implemented with recursion, it can also be done iteratively. By using a stack to keep track of the segments that need to be sorted, you can avoid the overhead of recursive function calls. This approach can lead to greater efficiency in certain programming scenarios.

Think of sorting your books not by repeatedly piling smaller stacks on top, but instead by using a tray to keep track of the segments you still need to organize. This way, you can make the process smoother without getting overwhelmed by too many smaller stacks.

So, in practice Quicksort is very fast, as we said the worst case happens very rarely. For this reason, typically Quicksort is a default algorithm that you see that people use when you have a built in sort function.

Because it performs well on average and is relatively straightforward to implement, Quicksort is often used as the underlying sorting algorithm in many programming languages and libraries. Its speed and efficiency make it a popular choice for built-in sort functionality.

Just like microwaves are a common tool for heating food because they are fast and efficient, Quicksort has become a go-to algorithm for sorting data in various applications due to its speed and reliability.

--