Chapter 7: Quicksort: Description, Performance, and Analysis

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement not replaced the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

Welcome back to the Deep Dive.

You know, we often talk about the kind of bedrock of computer science, those fundamental algorithms that make everything work, and today we're diving into one of those seemingly basic, but surprisingly intricate areas,

sorting algorithms.

You might think at first glance, all sorting is created equal, but as we'll see,

the real world performance could be wildly different from what the theory might suggest.

Yeah, that's a great point.

It's easy to get caught up in theoretical guarantees, like, you know, worst -case running times.

But what truly matters in practice is often how an algorithm behaves on average and even those subtle ways it interacts with the hardware.

Right, and that brings us to our topic for today, quicksort.

Now, this is an interesting one.

On paper, it has this potentially pretty bad worst -case performance.

It can bog down to big theta of n squared, which isn't exactly blazing fast.

Yet, despite this lurking worst case, quicksort is often the go -to algorithm when you need to sort things quickly in the real world.

It's almost paradoxical, right?

It is.

It raises a fundamental question.

Why do we trust an algorithm with a potentially slow worst case for so many critical applications?

Right.

So, our mission in this step dive is to really unravel the mystery of quicksort.

We want to understand its inner workings,

get an intuitive grasp of why it's so efficient on average, and appreciate the nuances that make it a practical champion.

And to do this, we're digging into a fantastic chapter that one of you, our listeners, shared with us, and it provides a systematic breakdown of quicksort, and we're going to follow that roadmap.

We'll start by clearly laying out how the algorithm works, then we'll build an intuition for its performance characteristics.

We'll also explore a clever trick called randomization, and finally delve into a more formal analysis to really nail down why it behaves the way it does.

So, get ready to really understand quicksort.

All right.

Let's get down to the nuts and bolts of the quicksort algorithm itself.

Much like merge sort, which we've discussed before, quicksort uses the divide -and -conquer strategy, but the way it achieves this division and conquering is quite unique.

The first key step in quicksort is the divide part, often referred to as partitioning.

This is where the algorithm starts to get interesting.

Imagine you have a disorganized array of elements.

Quicksort rearranges this array into two sub -rays, a low part and a high part, all relative to a chosen element called the pivot.

And the crucial thing about this partitioning is that everything in the low sub -ray will be less than or equal to the pivot, and everything in the high sub -array will be greater than or equal to it.

What's also important is that as a result of this partitioning, the pivot element ends up in its final sorted position within the array.

The algorithm also keeps track of the index where the pivot lands, which we can call Q.

Okay, so we've used the pivot to split our problem into two smaller sub -problems.

What's the next step in this divide -and -conquer dance?

That's the compare step.

Once we've partitioned the array around the pivot, quicksort then recursively calls itself on those two sub -rays, the low side and the high side.

It's the same quicksort process, just applied to smaller and smaller pieces of the original array.

Recursive calls, a classic sign of divide -and -conquer.

Now, what about the combine step?

With merge sort, we had that essential merging of the sorted sub -rays.

Does quicksort have a similar step?

Interestingly, no explicit combining is needed in quicksort, because the partitioning step already ensures that all elements smaller than the pivot are in one sub -array and all larger elements are in the other, and the pivot itself is in its correct sorted position.

Once the sub -rays are sorted, the entire array is sorted.

The work of putting elements in their correct relative order is done during the partition.

That's pretty elegant.

That is.

So the hard work of ordering happens during the divide phase.

Now, the chapter you shared mentions a procedure called quicksort of APR.

Can you break down what those letters mean?

Certainly, quicksort of APR is the procedure that sorts a specific portion of an array starting at index P and going up to index R.

So if you have an array A with N elements, let's say using one -based indexing from one to N, the initial call to sort the entire array would be quicksort of A1N.

Inside this procedure, it first checks if P is less than R.

If it is, meaning the sub -array has at least two elements, it proceeds with the partitioning and the recursive calls on the two resulting sub -arrays.

If P is not less than R, it means we have a sub -array with zero or one element, which is already sorted, so the procedure does nothing in returns.

Okay, that makes sense.

Now, the chapter really emphasizes that the work course of quicksort is the partition procedure of APR.

Let's really dig into that.

What exactly is its role?

The partition procedure is absolutely central to quicksort.

Its job is to take a sub -array A from P to R and rearrange it in place.

It selects an element within the sub -array as the pivot.

In the version described in the chapter, it consistently chooses the last element of the sub -array, A of R, as the pivot.

Then it cleverly reorganizes the sub -array so that all elements less than or equal to this pivot are moved to the beginning part of the sub -array and all elements greater than or equal to it are moved to the latter part.

Finally, it places the pivot element right in between these two sections at its correct sort of position within that sub -array and returns the index of this pivot.

Okay, so the last element is always the chosen pivot in this version.

How does it actually go about doing this rearrangement?

The partition procedure uses a neat technique with two indices, I and J.

It initializes an index I to P minus one.

Think of as marking the end of the low region.

The part of the sub -array we've already determined contains elements less than or equal to the pivot.

Then it uses another index J to iterate through the sub -array starting from P and going up to R minus one, stopping just before the pivot.

And what happens as J moves through the sub -array?

For each element A of J that J points to, the procedure compares it to the pivot X, which is A of R.

If A of J is less than or equal to the pivot, it means this element belongs in the low region.

So the procedure first increments I, effectively expanding the low region by one position, and then swaps the element at A of I with the element at A of J.

This places the smaller or equal element A of J into its correct low side position.

If A of J is greater than the pivot, it simply moves on to the next element by incrementing J as it's already in the correct relative region, the high side, which is implicitly being formed after the low side.

So it's like it's gradually building up the partitioned array as it scans through.

The chapter also mentions a loop invariant with three conditions and refers to tan, blue, and yellow regions as illustrated in figure 7 .2.

That sounds important.

It is crucial for understanding why partition works correctly.

The loop invariant essentially describes the state of the sub -array at the beginning of each iteration of the for loop, where J is moving.

It has three key parts.

The tan region, which spans from the starting index P up to the current value of I, contains all the elements that we've found so far to be less than or equal to the pivot X.

The blue region, which goes from I plus 1 up to J minus 1, contains all the elements that we found to be strictly greater than X.

And the yellow region is simply the pivot itself, located at the very end of the sub -array at index R.

The remaining part of the sub -array, from the current J up to R minus 1, consists of elements whose relationship to the pivot hasn't been determined yet.

Okay, so this invariant is set up before the loop begins.

Initialization.

It remains true after each time the loop runs.

Maintenance.

And when the loop finally ends.

Termination.

It gives us a state that helps us finish the partitioning correctly.

Exactly.

Initially, I is P minus 1 and J is P.

So both the tan and blue regions are empty, which satisfies the first two conditions.

The pivot is at A of R, satisfying the third.

During each iteration, as we discussed, if A of J is greater than X, we just extend the blue region, implicitly by moving J forward.

If A of J is less than or equal to X, we extend the tan region by incrementing I and swapping A of I with A of J.

This maintains the invariant throughout the loop.

When the loop finishes, J reaches R, meaning we've processed all elements except the pivot, and they are now in either the tan, low side, or blue high side region.

And then what happens to take the pivot into its rightful place?

After the loop completes, the pivot, which is still sitting at A of R, needs to be placed between the low region, elements less than or equal to X, and the high region, elements greater than X.

This is achieved by a final swap.

We swap the element at A of I plus 1 with the element at A of R.

Now all elements from P to I are less than or equal to the pivot at I plus 1, and all elements from I plus 2 to R, which were originally from I plus 1 to R minus 1 and have now shifted, are greater than or equal to the pivot.

The partition procedure then returns I plus 1, which is the new index Q of the pivot element.

So after partition is done, the pivot is in its correct sorted position within that subarray, and we have these two subarrays before and after the pivot that are now ready for the recursive calls.

The chapter also mentions in exercise 7 .1 -3 that partition on a subarray of size n takes big theta of n time.

Why is that the case?

That's because the partition procedure iterates through the subarray, excluding the pivot exactly once.

For each of the n minus 1 elements, it performs a constant amount of work, a comparison, and potentially a swap.

Since the amount of work per element is constant and we process each element once, the total time taken is directly proportional to the number of elements in the subarray, which is n minus 1.

Therefore, the running time is big theta of n.

Think of it like checking everyone's ID in a line.

The time it takes is proportional to the number of people in the line.

Okay, so we've got a solid understanding of how quick sort actually works.

Now let's get to the crucial part.

How well does it perform?

The chapter immediately jumps into how the balance of those partitions we just talked about significantly affects its speed.

Precisely.

The efficiency of quick sort is highly dependent on how evenly the partition procedure divides the array.

If we consistently manage to split the array into roughly equal halves, quick sort can be incredibly fast.

However, if the partitioning consistently results in one very large subarray and one very small or even empty one, the performance can suffer.

Okay, let's start by looking at the absolute worst case scenario.

What kind of partitioning would lead to the slowest possible performance for quick sort?

The absolute worst case partitioning happens when, at every step, the partition procedure produces one subarray with n minus one elements and the other with zero elements.

Imagine that the pivot you pick is always either the smallest or the largest element in the current subarray.

This means that one of the recursive calls will be on a subarray that's only one element smaller than the original, and the other recursive call will be on an empty subarray.

Ouch.

That sounds like we're not making much progress in reducing the problem size.

What's the resulting running time in this worst case scenario?

The chapter presents a recurrence relation that describes this situation.

T of n equals T of n minus one plus T of zero plus big theta of n, where T of n minus one represents the time to sort the large subarray.

T of zero is the constant time to sort the empty subarray, and big theta of n is the time spent in the partition procedure.

This simplifies to T of n equals T of n minus one plus big theta of n.

If you solve this recurrence, you'll find that it results in a running time of big theta of n squared.

You can think of it like this.

We do roughly n work at the first level, then roughly n minus one at the next, then n minus two, and so on down to one, which sums up to something proportional to n squared.

Big theta of n squared.

That's the same running time of insertion sort, which we know isn't the most efficient for large data sets.

The chapter points at a particularly ironic situation where this worst case occurs when the input array is already sorted.

It's funny because that's a case where insertion sort actually shines with an O of n time complexity, because it just needs to iterate through and confirm everything is in order.

Exactly.

In the worst case scenario, quicksort's performance is quite poor, no better than a very basic sorting algorithm.

Now let's look at the opposite end of the spectrum.

Okay.

What about the best case partitioning?

So the best case would intuitively be if the partition procedure perfectly bisects the array into two subproblems of roughly equal size, around n divided by two each time.

Yes.

In this ideal scenario, the recurrence relation for the running time becomes T of n equals two times T of n divided by two plus big theta of n.

The two times T of n divided by two comes from the two recursive calls on subarrays of size roughly n divided by two, and the big theta of n is still the cost of the partition procedure.

As the chapter mentions, if we apply the master theorem, a handy tool for solving recurrences of this form, this recurrence solves to big theta of n log n.

Big theta of n log n.

Now we're talking.

That's the same asymptotic performance as merge sort, which is known for its efficiency and generally considered very good for sorting.

So it seems like getting those balanced partitions is really the key to quicksort speed.

Absolutely.

And what's quite remarkable is that even partitionings that might seem somewhat unbalanced can still lead to excellent asymptotic performance.

The chapter gives a great example of a nine -to -one split.

At first glance, having one subarray nine times larger than the other feels quite lopsided.

It really does.

You'd naturally think that having such an uneven split at every level of recursion would lead to a slow algorithm.

But if we look at the recurrence relation for this case, T of n equals T of nine n divided by 10 plus T of n divided by 10 plus big theta of n, and we visualize the recursion tree as shown in figure 7 .4 in the chapter, we see something interesting.

While the tree might look a bit skewed, at each level of the recursion, the total amount of work done in partitioning across all the subproblems at that level is still big O of n.

What changes with the unbalanced split is the depth of the recursion tree.

However, even with a nine -to -one split, the depth remains logarithmic.

It's proportional to log base 10 ninths of n and log base 10 of n.

So even with this seemingly quite poor nine -to -one split happening at every level, the overall running time is still big O of n log n.

That's quite counterintuitive.

It is.

It really highlights that as long as the split has a constant proportionality, meaning that neither of the resulting sub -rays is a vanishingly small fraction of the original, the recursion tree will have a logarithmic depth.

And since we do linear work at each level, the overall time complexity remains big O of n log n.

The actual ratio of the split only affects the constant factor that's hidden within the big O notation.

This is a crucial insight into why quicksort can be so robust in practice.

That's a really important takeaway.

So achieving a perfect 50 -50 split at every step isn't strictly necessary for efficient O of n log n performance.

Now, the chapter then moves on to give us some intuition about the average case performance of quicksort.

It mentions making the assumption that all possible orderings permutations of the input array are equally likely.

Yes.

To analyze the average case behavior, this is a standard assumption we make.

Right.

In a typical run of quicksort on a randomly ordered input array, we won't consistently encounter the worst case scenario, always picking the smallest or largest element as the pivot, or even the best case scenario, always getting perfect splits.

Instead, we expect a mix of splits, some reasonably balanced good splits, and some more unbalanced bad splits occurring randomly throughout the recursion process.

Right.

And the chapter uses a helpful analogy here, talking about alternating between bad and good splits at different levels of the recursion.

Exactly.

Figure 7 .5 in the chapter illustrates this idea.

Imagine we have a particularly bad split at one level, say a worst case split, where we get sub -rays of size n minus 1 and 0.

Now, at the next level, if we happen to get a best case split on that larger sub -ray of size n minus 1, dividing it roughly in half, the chapter argues that the cost of that initial bad split can be, in a sense, absorbed by the efficiency gained in the subsequent good split.

So even if we have some bad luck with our pivot choices early on in the recursion, as long as we encounter some good pivot choices later,

the overall performance tends to gravitate towards that O of n log n that we saw in the best case scenario.

It's like the good luck averages out the bad luck.

That's the basic intuition.

While a rigorous mathematical analysis of the average case can be quite involved, this idea of alternating good and bad splits helps us understand why the average case performance of quicksort is much closer to its best case performance, big O of n log n, than to its worst case performance, big O of n squared.

The occasional unbalanced partition doesn't fundamentally change the logarithmic depth of the recursion tree in the average case.

That makes a lot of sense intuitively.

Now, the chapter then introduces a randomized version of quicksort.

What's the motivation behind randomizing the algorithm?

The average case analysis we just discussed relies on the assumption that all input permutations are equally likely.

However, in real world applications, this assumption might not always hold.

We could encounter input arrays that are already sorted or nearly sorted, which as we saw, can lead to the worst case behavior in the deterministic version of quicksort, where we always choose the last element as the pivot.

Randomization is a powerful technique we can use to achieve good expected performance across all possible inputs without relying on any assumptions about the initial ordering of the data.

So how does this randomized version work?

Does it involve shuffling the array before sorting, or is it something different?

The chapter describes a clever approach that's slightly different and often easier to analyze.

Instead of always selecting the last element as the pivot, the randomized partition procedure randomly chooses an index i within the current subarray, from p to r inclusive.

It then simply swaps the element at this randomly chosen index a of i with the last element a of r.

After the swap, the standard partition procedure, which always uses the last element as the pivot, is called.

The effect is that we're now using a randomly selected element as the pivot for that particular partitioning step.

I see.

So the only change is in how the pivot is chosen.

We're essentially picking a random element to be the pivot before we do the partitioning.

Precisely.

The randomized quicksort procedure is then exactly the same as the original quicksort, except that it calls randomized partition to select the pivot instead of the deterministic partition.

By introducing this randomness into the pivot selection at each step, we make it highly unlikely that any specific input will consistently trigger the worst case scenario.

It's like shuffling a deck of cards before you play a game to avoid consistently getting a bad hand.

That's a great analogy.

It makes the benefit of

randomization very clear.

Now, after introducing this randomized version, the chapter moves into a more formal analysis of quicksort.

It revisits the worst case analysis, but with a more rigorous approach, and then it delves into the expected running time of this randomized version.

Yes.

Even though randomization helps us achieve good expected performance,

it's still possible, though highly improbable, to encounter a sequence of random pivot selections that lead to worst case partitioning.

So, the chapter first provides a more formal proof of the big theta of n squared worst case running time that applies to both the deterministic and the randomized versions.

It then focuses on the more interesting part, the expected running time of the randomized quicksort.

Can you give us a brief overview of how that formal worst case proof works?

Formal proof uses the substitution method.

We start with the worst case recurrence relation discussed earlier.

T of n equals the maximum of t of q plus t of n minus 1 minus q, close parentheses, plus big theta of n, where q is the size of the smaller of the two subarrays produced by partitioning.

So, 0 is less than or equal to q, which is less than or equal to n minus 1.

We then make the inductive hypothesis that t of n is less than or equal to c n squared for some constant c greater than 0.

By substituting this hypothesis back into the recurrence and performing some algebraic manipulations, we can show that this inequality holds if we choose c large enough.

The key step is recognizing that the expression q squared plus open parentheses n minus 1 minus q, close parentheses, squared is maximized when q is either 0 or n minus 1, which corresponds to the worst case split.

This confirms that the worst case running time is indeed big O of n squared.

Since we already saw a case, sorted input, that achieves big theta of n squared, the worst case time complexity is big theta of n squared.

Okay, so the formal proof reinforces our understanding of the quadratic worst case.

Now let's get to the more exciting part, the expected running time

of randomized q squared.

How does the chapter tackle that?

This is where the analysis gets quite elegant.

The chapter shifts focus from directly analyzing the number of recursive calls and their depth to analyzing the expected number of comparisons performed between elements during the entire sorting process.

Okay, why the shift to counting comparisons?

Because as stated and proved in Lemma 7 .1, the running time of quicksort is directly related to the number of element comparisons.

Specifically, it shows that the total running time is big O of n plus x, where x is the total number of comparisons made.

The partitioning step itself takes linear time, big theta of n, plus the time spent on comparisons.

Since every element is compared with the pivot during partitioning, the total running time is tightly bound to the total number of comparisons across all levels of recursion.

Okay, so the goal is to figure out the expected value of x, the total number of comparisons.

How does the chapter approach calculating this expected value?

To simplify the analysis, the chapter introduces the idea of referring to the elements by their sorted rank.

Let's say we have the sorted sequence of the n distinct elements as z sub 1 is less than z sub 2 is less than dot dot dot is less than z sub n.

Now Lemma 7 .2 provides crucial insight.

Two elements z sub i and z sub j, where i is less than j, are compared during the execution of quicksort if and only if one of them is chosen as a pivot before any other element that lies strictly between them in the sorted order, i .e.

any element in the set z sub i g equals open brace z sub i comma z sub i plus 1 comma dot dot dot comma z sub j close brace.

Furthermore, it states that any two elements are compared at most ones.

That's a really clever observation.

It seems to simplify the problem of counting comparisons

significantly.

So a comparison between two elements happens if and only if one of them is the first pivot we pick from the entire group of elements that lie between them in the sorted order.

Exactly.

Now using this insight, Lemma 7 .3 calculates the probability that two specific elements z sub i and z sub j, where i is less than j, are compared because in randomized quicksort at each partitioning step, any element within the current sub array is equally likely to be chosen as the pivot.

When we consider the set of elements z sub i, the first pivot chosen from this set is equally likely to be any one of the j minus i plus 1 elements in it.

For z sub i and z sub j to be compared, either z sub i must be the first pivot chosen from z sub i with probability 1 divided by j minus i plus 1 close parentheses,

or z sub j must be the first pivot chosen from z sub i, also with probability 1 divided by open parentheses j minus i plus 1 close parentheses.

Since these are mutually exclusive events, the total probability that z sub i and z sub j are compared is the sum of these probabilities, which is 2 divided by open parentheses j minus i plus 1 close parentheses.

Okay, so we now have the probability of any two specific elements being compared.

How do we use this to find the expected total number of comparisons?

This is where we use the concept of indicator random variables.

For every pair of elements, open parentheses z sub i comma z sub j close parentheses, where 1 is less than or equal to i, which is less than j, which is less than or equal to n, we define indicator random variable x sub i, which is equal to 1 if z sub i and z sub j are compared during the algorithm and zero otherwise.

The total number of comparisons x is then simply the sum of all these indicator variables over all possible pairs open parentheses i comma j close parentheses with i less than j.

By the principle of linearity of expectation, the expected value of the total number of comparisons e open bracket x close bracket is equal to the sum of the expected values of each individual indicator variable x sub i, and the expected value of an indicator variable is just the probability that the event it indicates occurs.

So e open bracket x sub i close bracket equals the probability that z sub i is compared to z sub j close parentheses equals 2 divided by open parentheses j minus i plus 1 close parentheses.

Okay, so the the expected total number of comparisons e of x is the sum of 2 divided by j minus i plus 1 over all pairs of indices ij,

such that 1 is less than or equal to i which is less than j which is less than or equal to n.

How do we how do we go about evaluating this this sum?

The chapter then walks through the mathematical steps to evaluate this double summation.

This involves a clever change of variables often letting k equal j minus i, and using the well -known bound on the harmonic series the sum 1 divided by k from k equals 1 to n is approximately the natural log of n plus big o of 1 which is big o of log n.

After performing these summations the result is that the expected number of comparisons e open bracket x close bracket is found to be big o of n log n.

And since we established earlier via lemma 7 .1 that the running time of quick sort is big o of n plus x and now we found that the expected value of x is big o of n log n, it follows that the expected running time of randomized quick sort on an imprint of n distinct elements is also big o of n log n.

That's a that's a fantastic and powerful result.

It truly is.

It shows that on average even though worst case scenario can be as bad as quadratic time by simply introducing a random choice of pivot at each step the expected performance of quick sort becomes remarkably efficient matching the asymptotic performance of the best comparison based sorting algorithms like merge sort.

So just to bring it all together quick sort's efficiency really hinges on getting reasonably balanced partitions.

While it has the potential for a slow quadratic time in the worst case its average case performance and more importantly its expected performance when we use randomization is excellent at big o of n log n.

That's an excellent summary and this strong expected performance is a major reason why quick sort is so widely used in practice.

Beyond just the good average case time complexity the chapter also briefly touched upon in the introduction that quick sort often has smaller constant factors hidden within the big o notation compared to other big o of n log n algorithms like merge sort.

It performs the sorting in place meaning it doesn't require significant additional memory and it tends to exhibit good locality of reference which makes it efficient in virtual memory environments.

All those practical advantages combined with the solid expected performance we've just unpacked really solidify quick sort's position as a workhorse in the world of sorting algorithms.

It's a great example of how understanding the nuances of an algorithm beyond just its worst case behavior is crucial for appreciating its real world value.

Absolutely.

It highlights the beautiful interplay between theoretical analysis and practical considerations in computer science.

This has been a truly enlightening deep dive into the intricacies of quick sort.

It's fascinating to see how such a seemingly simple algorithm has so much depth and nuance.

Now for our final thought for you our listener.

Consider the power of randomness in algorithm design.

How can introducing a bit of randomness lead to significantly improved expected performance even if the worst case possibilities remain?

Are there other areas in computer science where randomization plays a similar role in treating robust and efficient solutions?

It's definitely something

worth pondering.

Thanks for joining us on this deep dive.