Choosing a Pivot and Partitioning Everything Around It

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 16.3 Free with a free account

Choosing a Pivot and Partitioning Everything Around It

Data Structures and Algorithms · Chapter 16: Sorting, Selection, and Text ProcessingSection 16.3 · lesson 69 of 878 min · free with a free account

← Merge Sort: Split in Half, Sort Each Piece, CombineNext lesson: Insertion Sort: Sliding Each Element into Place →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

How quicksort picks a pivot and partitions with Lomuto and Hoare.

  • Trace Lomuto and Hoare partitioning on a small array
  • Compare first-element, random, and median-of-three pivot choices
  • Explain quicksort's best, average, and worst-case running times
  • Limit quicksort's recursion depth by recursing on the smaller part first

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,144 words). Read along, or search it.

Opening Question

Lining People Up Around One Reference

Imagine lining up 200 people by height. Here's a practical way. Pick one person as a reference, and ask everyone shorter to stand on their left, and everyone taller on their right. Neither group is in order yet. But the reference person is already standing in exactly the right spot. And each group can be sorted on its own, with the same trick. That's quicksort. The reference is called the pivot, and splitting around it is called partitioning.

Core Idea

Choose, Partition, Then Sort Each Side

Quicksort repeats three steps on every part of the array that still holds more than one key. Choose a pivot. Partition the part around it. Then sort each side the same way. Partitioning doesn't sort either side. It only guarantees that every key on the left is smaller than every key on the right, with the pivot in its final place between them. So once both sides are sorted, the whole array is sorted, with no merging step. And a part of zero or one key is already in order, so the recursion stops there.

Lomuto Scheme

Pivot at the End, Boundary at the Front

The Lomuto scheme is the easiest partition to follow. The pivot is the last key. A boundary i marks the end of the group of smaller keys at the front. A second pointer, j, scans the rest. Whenever j meets a key smaller than the pivot, that key is swapped into the smaller group, and the boundary moves one step right. When the scan ends, the pivot is swapped into the slot at i, exactly where it belongs. The method returns that index.

Worked Example

Partitioning Around the Pivot 6

Run it on 7, 2, 9, 4, 3, 8, with the pivot 6. Each line shows one step of j. 7 is kept. 2 is smaller, so it swaps to the front, and i becomes 1. Then 4 and 3 are swapped in, and i reaches 3. Finally, the pivot swaps into index 3: 2, 4, 3, then 6, then 9, 8, 7. The left side isn't sorted, but every key there is smaller than 6. One scan of k keys made k minus one comparisons with the pivot. So a partition costs time proportional to the size of the part.

Quick Check

Lomuto on Six Keys With Pivot 5

Quick check. Apply the same Lomuto partition to 4, 7, 1, 6, 2, 5. The pivot is the last key, 5. What's the array afterward? Pause and predict. 4, 1, 2, then 5, then 7, 6. The smaller keys, 4, 1, and 2, are gathered at the front in the order j finds them. The final swap trades the pivot with the 6 at index 3, so the larger side reads 7, 6. Nothing sorted either side: that's the recursion's job.

Hoare Scheme

Two Pointers Walking Toward Each Other

The Hoare scheme, the original design from the inventor of quicksort, uses two pointers that start at opposite ends, and walk toward each other. The left one skips keys smaller than the pivot. The right one skips keys larger than it. When both stop, they swap, putting one misplaced key into each half. The scan ends when the pointers meet or cross. Here the pivot comes from the front, and it doesn't necessarily finish in its final place. Hoare returns a split point instead.

Quick Check

Hoare Partition on Four Equal Keys

Quick check. Run Hoare's partition on four equal keys: 5, 5, 5, 5. The pivot is 5 too. Which split point does it return? Pause and predict. One, right in the middle. Both pointers stop on every key equal to the pivot, so they swap and meet halfway: parts of two and two. Lomuto would put the pivot at index zero, since no key is ever smaller, leaving one side empty. That difference matters a lot, as the measurements show.

Pivot Choice

First, Random, or Median of Three

Both schemes work with any key as the pivot. The real question is which key to pick. Ideally it lands near the middle of the part, splitting the work evenly. The first element costs nothing, but it's the worst possible pivot on sorted data. A random element can't be beaten reliably by any fixed input. And median of three takes the middle value of the first, middle, and last keys. With Lomuto, the chosen key is simply swapped to the end before partitioning.

Measurement

Sorted Input Breaks the First-Element Pivot

This program sorts four kinds of input, 2,000 keys each, with each rule. Each cell shows comparisons, then the deepest recursion. On sorted or reversed keys, the first element needs 1,999,000 comparisons, and recursion 1,999 levels deep. That's about eighty times its cost on random keys. Random and median-of-three pivots stay within a small factor of n log n, about 22,000, on every ordered input. That's far from quadratic. But when all keys are equal, Lomuto is quadratic under every rule: no key is smaller than the pivot, so one side is always empty. Only Hoare, which splits equal keys evenly, stays fast.

Running Time

Best, Worst, and Average Splits

So the cost depends entirely on how evenly each partition splits its part. In the best case, every pivot is the middle key: about log n levels, each handling n keys, so about n log n. In the worst case, every pivot is the smallest or largest key. The parts shrink by one key at a time, and the total is n times n minus one, over two. The average is close to the best case. Over random orderings, it's about 1.39 n log n. In one test on a million random keys, the deepest recursion was 53 levels, nowhere near n.

Stack Depth

Recurse on the Smaller Part First

Quicksort sorts in place: it only swaps keys inside the array. Its only extra memory is the call stack, one frame per open level of recursion. So depth is the number to watch. Here, 50,000 sorted keys with the first-element pivot: each split removes one key, so plain recursion would go 50,000 levels deep. The fix: recurse only on the smaller part, and loop back for the larger one. Each recursive call gets at most half the keys, so the depth can't exceed log n. Run it. The plain version overflows the stack. The safe version reached depth one. But it still made over 1.2 billion comparisons. The trick protects memory, not time. Only a good pivot protects time.

Properties

Fast and In Place but Not Stable

To round out the picture: quicksort is fast on average, sorts in place, and with the smaller-part trick, needs only order log n stack. It isn't stable: a swap can carry a key past an equal one. And its worst case is still quadratic. When a strict guarantee is needed, heap sort, from chapter 13, gives n log n in every case.

Key Takeaways

Quicksort in Brief

To sum up. Quicksort picks a pivot, partitions around it, and sorts each side. One partition puts the pivot in its final place. Lomuto is easy to follow. Hoare moves two pointers inward, and copes far better with equal keys. First-element pivots fail on sorted data. Random and median-of-three pivots stay near n log n. And recursing on the smaller part first keeps the depth at log n, protecting memory, but not time.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Choosing a Pivot and Partitioning Everything Around It

What is partitioning in quicksort?
Partitioning rearranges part of an array around a chosen key, the pivot, so that smaller keys end up on its left and larger keys on its right. Partitioning does not sort either side. Quicksort then sorts each side the same way, and because every left key is no larger than every right key, no merge step is needed. Partitioning k keys takes time proportional to k.
What is the difference between Lomuto and Hoare partitioning?
Lomuto partitioning takes the last key as the pivot, scans with one pointer, swaps smaller keys into a growing group at the front, and finally swaps the pivot into its final index. Hoare partitioning moves two pointers inward from both ends, swaps misplaced pairs, and returns a split point where the pivot need not be final. Hoare copes far better with equal keys, splitting an all-equal array evenly.
What is quicksort's worst case and how can it be avoided?
Quicksort's worst case is quadratic, n(n-1)/2 comparisons, and it happens when every pivot is the smallest or largest key, so each part shrinks by just one key. A first-element pivot triggers it on sorted or reversed input. Random or median-of-three pivots keep the cost near n log n on ordered inputs. Over random orderings, quicksort averages about 1.39 n log n comparisons.
How do you keep quicksort's recursion depth at log n?
Recurse only on the smaller part after each partition, and loop back to handle the larger part. Each recursive call then gets at most half the keys, so the stack depth cannot exceed about log2 n. This protects memory, not time: on 50,000 sorted keys with a first-element pivot, the safe version avoids a stack overflow but still makes over 1.2 billion comparisons.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →