16.1.6. Randomized Algorithm

Now, the behavior of this algorithm is not fixed, it depends on how this die rolls. So, this is a different type of algorithm called a randomized algorithm. So, you can now implement Quicksort in a randomized speed with a very simple randomization step, namely just pick the pivot at random at each called Quicksort.

In this chunk, we learn about randomized algorithms, specifically how they work in the context of Quicksort. Unlike deterministic algorithms, which follow a fixed sequence of steps, a randomized algorithm uses random numbers or random selections during its execution. In Quicksort, instead of consistently choosing the same pivot element (like the first or last element), we pick the pivot randomly from the available elements. This randomness reduces the chance of encountering worst-case scenarios, leading to better performance on average.

You can think of choosing a pivot element like rolling a die. When you roll a die, any number from one to six appears with equal chances. If you were sorting a stack of cards, instead of always picking the top card to be the pivot, sometimes you'd choose a random card from the stack, which could lead to a better division of the other cards.

So, you can prove that the expected running time across all possible random choices I make for the pivot, the expected running time is order n log n. So, this is a very simple, this is a kind of a dual result to the fact of the average cases n log n.

This chunk explains the average case complexity of randomized Quicksort. The average case running time is described as O(n log n), indicating that when we look at all possible ways the algorithm could run with random pivot choices, its performance is quite efficient on average. This understanding is crucial as it shows that even though the worst-case scenario can lead to O(n^2) performance, through randomization, we can expect a better, efficient performance under typical conditions.

Imagine you're organizing books on a shelf. If you always start sorting from the smallest or largest book, you might take longer. But if you randomly select a book to compare first, you'll likely divide books into smaller, more manageable groups more quickly. This random choice tends to lead to a faster overall sorting time on average, just like randomized Quicksort.

So, what we are saying is that for any fixed strategy, if I tell you in advance that I am always going to compute the position of the pivot in a fixed way, then by working backwards you can always ensure that the position in the current problem, you have a worst case that is an extreme input.

Here, the focus is on the issue of fixed pivot selection strategies leading to poor performance in certain cases. If you always use a set method for selecting the pivot (like always choosing the first element), you can predictably create scenarios that lead to the worst performance. The randomized approach, where the pivot is selected randomly for each call, prevents the algorithm from being susceptible to such poor cases by varying the pivot selection each time.

Think of brewing coffee. If you always brew with the same amount of water and same type of coffee every time, you might discover that certain amounts work poorly with specific types of coffee. Instead, if you vary the amount and choose randomly, you might find a consistently better flavor without predictable failures.

So, you can actually exploit this average case behavior in a very simple manner. So, why does this worst case occur? The worst case occurs, because the pivot that we choose could be a bad pivot.

This chunk explains the benefits of the randomized approach in Quicksort. By introducing randomness in selecting the pivot, we exploit the average-case behavior of the algorithm, leading to efficient performance without the predictable downsides of a fixed selection strategy. This avoids the pitfalls leading to worst-case performance in deterministic implementations.

Imagine a game where you have to guess the card someone is thinking of, picking from a shuffled deck versus a sorted one. If you randomly pick cards, you're far less likely to strike out on your guesses compared to sticking only to obvious choices like picking from the top. This randomness mimics how randomized Quicksort operates to ensure efficient sorting most of the time.

--