Sorting and Selection in Practice, Explained

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

Sorting and Selection in Practice

Data Structures and Algorithms · Chapter 16: Sorting, Selection, and Text ProcessingSection 16.7 · lesson 73 of 8713 min · free with a free account

← Finding Another Slot When the Home Slot Is TakenNext lesson: Strings: Why Text Needs Its Own Data Handling →

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

Multi-key sorting, quickselect, top-k heaps, and non-comparison sorts.

  • Sort records by several keys with a comparator chain or stable passes
  • Find a k-th smallest value or a median with quickselect
  • Find the k largest values of a stream with a min-heap
  • Explain when counting, radix, and bucket sort beat comparison sorts

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,857 words). Read along, or search it.

Opening Question

Median Versus Mean Response Time

A support team logs nine response times, in milliseconds. Seven sit near 200. Two are slow: 954, and 3,120. Their average is about 609 milliseconds, a time that describes none of the visits. The median, the middle value once they're sorted, is 208. That's the honest summary. But do we have to sort everything to find it?

Roadmap

Records, Selection, and Library Sorts

Real data comes as records, sorted by several keys. And often we want one value, like a median, or the top ten of an endless stream. Some sorts never compare keys at all. And Java's own sorts make choices worth knowing.

Multiple Keys

Chaining Comparators for Several Keys

Eight employees arrive in no order. We want them grouped by department, the highest salary first inside each, and ties broken by name. The fields that decide the order are called keys. The first is the primary key. Later keys only break ties. In Java, a record holds named fields, and a Comparator describes the order. Comparator.comparing starts the chain with the primary key. Each thenComparing adds a key that's used only when every earlier key ties. Reverse order flips one key, putting high salaries first. Run it. Departments come out alphabetical, and salaries fall inside each. Ila and Kabir both earn 48,000, so the name puts Ila first.

Stable Passes

Least Important Key First

There's a second route to the same order. Sort by the least important key first, then by the next one, and finish with the primary key. Here, pass one sorts by name, and pass two by department. Each pass must be stable: records with equal keys keep the order they already had. Run it. After pass two, the names are still alphabetical inside each department. And the result matches a single comparator chain exactly. That works only because Arrays.sort on objects is stable. Make the second pass a selection sort, which isn't, and Chen jumps ahead of Arjun.

Common Mistake

Subtraction Overflows in a Comparator

A comparator returns a negative number when the first value comes first, zero for a tie, and a positive number otherwise. So subtracting, p minus q, looks tempting. It works for small numbers. It fails when the subtraction overflows, and wraps around to the wrong sign. Compare two billion with minus two billion. The true difference doesn't fit in an int, so the result comes out negative. The sort then leaves the array unsorted, with no error at all. Integer.compare gets it right. In our test of 200 random arrays of a thousand ints, every one failed. Most came back wrongly sorted, without a word. A few threw an exception saying the comparison method violates its general contract.

Quick Check

The Last Stable Pass Wins

Quick check. A clerk wants six people listed by city, with ages rising inside each city. She sorts by city first, then by age. Both passes are stable. What order comes out? Pause and predict. By age, with equal ages ordered by city. The last pass always wins: it acts as the primary key. Agra 22 comes before Pune 22 only because the first pass put Agra first, and the stable second pass kept it there. To list by city, she must sort by age first, and by city last.

Selection Problem

Finding the Value at Position k

Back to the response times. Their median is one case of the selection problem: find the value that would sit at position k, if the array were sorted. We count k from one, so k equals one asks for the smallest. Sorting solves it in n log n time. But we don't need the values around the answer to be in order. That's the opening for something faster.

Quickselect

Partition and Keep Only One Side

Quickselect borrows quicksort's partition. Pick a pivot, and move every smaller value to its left. The pivot lands in its final place, at position p. If p is the target, the pivot is the answer. If the target lies left of p, the right side can't hold it, so it's dropped. Otherwise the left side goes. Quicksort continues on both sides. Quickselect keeps only one, which is why it does less work. Run it on nine values, asking for the 4th smallest. It finds 4, after two partitions and only 11 comparisons. Look at the array afterward. Only the answer is trustworthy. The rest is partly ordered, so work on a copy to keep the original.

Medians

Odd and Even Counts

For the median, ask for the middle position. With nine response times, that's the 5th smallest, and one call does it. With an even count, the median is the average of the two middle values, so it takes two calls. Both work on one copy, with a random pivot. Run it. The median is 208, and the mean nearly 609. Add a tenth time, 195, and the median becomes 205.5: the average of 203 and 208. Taking just one of the two middle values would be a common mistake.

Running Time

Linear on Average With a Random Pivot

Each partition reads its range once, but the ranges keep shrinking. If pivots land away from the ends, the total work is a constant times n. In our runs with a random pivot, quickselect needed between three and four comparisons per element, at a thousand values or at a million. Sorting a million values with Arrays.sort needed about 18.6 per element. A fixed pivot has a trap, though. For the median of 2,000 sorted values, always pivoting on the last element cost 1,500,499 comparisons. Every pivot was the largest value left, so each range shrank by one. A random pivot needed fewer than 7,000.

Top Values

A Min-Heap for the Largest Values

A related question: report the k largest values of a huge collection, or of a stream that never ends. Quickselect needs everything in memory. A heap needs only k places. Keep a min-heap of the k largest values seen so far. Its top is the weakest member of the current top k. While the heap holds fewer than k values, add the new one. Once it's full, a new value gets in only if it beats the top, which is removed. Java's PriorityQueue is a min-heap by default. Run it on a stream of seven values, with k equal to three. The answer is 20, 15, 12. Most values never get past the top. In our run on a million shuffled values, only 121 ever entered a heap of ten. So the cost is close to one comparison per value.

Comparison

Three Tools for Selection

So three tools answer selection questions. Sorting costs n log n, but then any position can be read. Quickselect is linear on average, but it needs the data in memory, and it rearranges it. A heap of size k costs n log k, keeps just k values, and it works on a stream.

Counting Sort

Counting Keys in a Small Range

Every sort so far compares pairs of keys, and any such sort needs about n log n comparisons in the worst case. The next three avoid that limit. They use a key's value instead. Counting sort suits whole-number keys in a small known range, like exam scores from 0 to 100. First, count how many records have each score. A running total then turns those counts into starting positions in the output. A left-to-right scan drops each record into its score's next free slot. So equal scores keep their order, and the sort is stable. Run it. Asha, Cara and Farid all scored 85, and they keep their arrival order. The cost is order n plus m, for m possible keys. But a score of 101 falls outside the counts, and the program stops with an index out of bounds.

Radix Sort

One Digit at a Time

When the key range is too large for one count array, radix sort works one digit at a time, starting from the least significant digit. Each pass is a stable counting sort on one digit. Here the ones digit goes first, then the tens, then the hundreds. Run it on eight numbers. After the ones pass, 170 and 90 lead, since both end in zero. After the tens pass, numbers with equal tens digits are still in ones order. That's stability at work. The hundreds pass finishes the job. The cost is order d times n plus b, for d digits in base b. Real code uses 8-bit digits: 256 counters, and four passes for an int. One caution: a negative value gives a negative digit, and the count array index fails. Shift or split the values first.

Quick Check

The First Radix Pass

Quick check. Take 53, 18, 41, 13, and 50. Run only the first radix pass: the stable counting sort on the ones digit. What order comes out? Pause and predict. 50, 41, 53, 13, 18. The pass looks only at the last digit: zero, one, three, three, eight. 53 and 13 tie on three, so they keep their arrival order, with 53 first. Putting 13 ahead is the tens pass's job.

Bucket Sort

Evenly Spread Real Numbers

Bucket sort suits real numbers spread evenly over a known range, say from zero up to one. Split the range into n equal buckets. Drop each value into its bucket, sort each small bucket with insertion sort, then read the buckets in order. Speed depends entirely on the spread. In one test on a million values, even data cost 0.45 comparisons per element. Data piled up near zero cost 278 per element, because one bucket held over 31,000 values.

Measurement

Faster on the Right Data Only

On the data each was made for, all three beat Arrays.sort. In one test at a million values, counting sort was about 28 times faster. Radix sort was about 7 times faster, and bucket sort about 3. But each needs extra memory, and each breaks on the wrong data: keys out of range, negative numbers, or skewed values.

Java Library

Dual-Pivot Quicksort and TimSort

In everyday code, the best sort is usually the one Java already provides. For primitive arrays like int, Arrays.sort is a dual-pivot quicksort. Stability can't matter there, since equal ints can't be told apart. For objects, the specification requires a stable sort, but leaves the algorithm open. This program peeks. Its comparator throws an exception, and we print the library methods it passed through. In Java 21, it's TimSort.

TimSort

Finding Runs Already in Order

TimSort looks for runs, stretches of the input already in order, and merges them. So order that's already there makes it fast. This program sorts 100,000 boxed ints three ways, counting the comparator's calls. Random order takes 15.35 comparisons per element. Ascending or descending input takes just one. A single pass finds one run, and descending runs are simply reversed. That's why sorting a list that's almost in order, say with a few new items at the end, costs very little.

Decision Guide

Which Method for Which Job

So which method for which job? For records in memory, call the library sort, and spend the effort on a correct comparator. For one k-th value or a median, use quickselect with a random pivot. For the top k of a stream, a min-heap of size k. Small integer ranges suit counting sort. Fixed-width keys suit radix sort, and evenly spread reals suit bucket sort. Data too large for memory needs the external methods of lesson 17.10.

Key Takeaways

Sorting and Selection in Brief

To sum up. For several keys, use one comparator chain, or stable passes, least important key first. Never subtract ints in a comparator: use Integer.compare. Quickselect finds a k-th value in linear time on average, and a min-heap of size k finds the top k of a stream. Counting, radix and bucket sort skip comparisons, but only on the right data.

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 Sorting and Selection in Practice

How do you sort by multiple fields in Java?
Build one Comparator chain: Comparator.comparing takes the primary key, and each thenComparing adds a key used only when every earlier key ties. A single key can be reversed, for example to put high salaries first. Alternatively, sort in stable passes from the least important key to the primary key. Arrays.sort on objects is stable, so both routes give the same order.
Why shouldn't a Java comparator subtract two ints?
Subtracting two ints in a comparator can overflow and wrap around to the wrong sign. Comparing 2,000,000,000 with -2,000,000,000 has a true difference of 4,000,000,000, which does not fit in an int, so the result comes out negative. The sort may then return wrongly ordered data with no error, or throw an exception saying the comparison method violates its general contract. Use Integer.compare(p, q) instead.
What is quickselect?
Quickselect finds the value that would sit at position k in sorted order without sorting the whole array. Like quicksort, it partitions around a pivot, which lands in its final position p. If p is the target, the pivot is the answer; otherwise it keeps only the side that holds the target. With a random pivot it runs in linear time on average, but it rearranges the array, so work on a copy.
How do you find the k largest values in a stream?
Keep a min-heap holding the k largest values seen so far; its top is the weakest member of the current top k. Add values freely until the heap holds k, then admit a new value only if it beats the top, which is removed. Java's PriorityQueue is a min-heap by default. The cost is O(n log k) with only k values in memory, so it works on an endless stream.

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 →