UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 11.5 Free with a free account
Rearranging Positional Collections into Order
Data Structures and Algorithms · Chapter 11: Dynamic Lists, Iterators, and the Collections FrameworkSection 11.5 · lesson 48 of 8711 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Why Hierarchies Represent Nested Relationships →← A Tour of Java's Pre-Built Collection ToolsNext lesson: Why Hierarchies Represent Nested Relationships →
In this lesson
Sorting Java lists with Comparable, Comparator and stable library sorts.
- Implement compareTo and write Comparators as lambdas or method references
- Chain comparators with comparing and thenComparing for multi-field ordering
- Explain stability and how it affects ties, reversing and multi-pass sorts
- Identify pitfalls such as subtraction overflow, unmodifiable lists and null elements
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,490 words). Read along, or search it.
Opening Question
Telling Java What Order Means
An ArrayList keeps each element in whatever position you gave it. Often you want a different arrangement: students by name, orders by date, scores from highest to lowest. Java can rearrange a list in a single line, but only if you tell it what in order means for your data. This lesson is about giving that instruction, and understanding what comes back.
Worked Example
A Comparable Student Type
To sort objects, Java must answer one question again and again: of these two elements, which comes first? There are two places the answer can live. Here's the first, in a small Student type with a name, a year, and a GPA. Student implements Comparable, and its compare to method compares names. That makes alphabetical by name its natural order. This static method builds the starting list: Dee, Eli, Ava, Ben, Fay and Cy. We'll rearrange it many ways.
Comparison Contract
The Sign of the Result Decides
A comparison method receives two elements, and returns an int. The sign of that int is the answer. Negative means the first element goes first. Positive means the second goes first. And zero means a tie.
Examples
Comparing Ava, Ben and Cy
Ava compared to Ben gives minus one. Ben compared to Ava gives one, and Ava to itself gives zero. Ava compared to Cy gives minus two. Only the sign counts: the size carries no extra meaning. Double compare and Integer compare follow the same contract.
Two Approaches
Comparable Versus Comparator
The second place the answer can live is a Comparator: a separate object whose only job is to compare two elements. Comparable is a contract a type signs once, with compare to. Strings, integers and doubles already have it. A Comparator lives outside the type, with a method called compare. So you can write as many as you like: by year, by GPA, by length of name. You can even order a type you didn't write, like String, any way you like.
Natural Order
Capitals Before Lowercase Letters
Natural order isn't always what you expect. For text, it's dictionary order of character codes. That puts every capital letter before every lowercase letter. So cy, Bea, adam and Zed sort as Bea, Zed, adam, cy. String's case insensitive order, a ready-made Comparator, gives adam, Bea, cy, Zed. Text that looks like numbers is sorted as text, too. Nine, one hundred, two and ten come out ten, one hundred, two, nine. Store them as ints, and they sort correctly: two, nine, ten, one hundred.
Quick Check
Sorting Mixed-Case Product Codes
Quick check. A list holds three product codes: lowercase b2, capital B10, and lowercase a7. It's sorted in natural order, and printed. What's printed? Pause and predict. B10, then a7, then b2. A capital B has a smaller character code than any lowercase letter, so B10 comes first. Then a7 comes before b2, by their first letters. The digits never got a say. The first option reads the digits as numbers and ignores case. The third is the case-insensitive order. Natural order does neither.
Sorting Methods
Sorting in Place With No Return Value
Java has two entry points for sorting a list. Collections.sort of a list uses natural order, so the elements must be Comparable. List.sort takes a Comparator, and passing null means natural order. Collections.sort also accepts a Comparator, as a second argument. Sorting the starting list by its natural order gives Ava, Ben, Cy, Dee, Eli, Fay. The sort works in place: the same list object is rearranged, and nothing is returned. So assigning its result to a variable won't even compile. To keep the original order, sort a copy. Here the copy is alphabetical, while the source still reads Dee, Eli, Ava.
Failure Cases
Unmodifiable Lists and Null Elements
The same program tries three lists that can fail. A list from List.of can't be changed, so sorting it throws an unsupported operation exception. A list from Arrays.asList can't grow, but its items can move, so it sorts normally. And a null element breaks a natural-order sort with a null pointer exception. Nulls first, wrapped around natural order, puts the null at the front.
Compile Error
Sorting a Type That Is Not Comparable
One more failure happens before the program even runs. This Plain type isn't Comparable, and no Comparator is given. The compiler refuses: no suitable method found for sort. The upper bound, Comparable, is the clue: the elements must be Comparable. The fix is to make the type implement Comparable, or to pass a Comparator.
Comparator Syntax
Anonymous Class, Lambda, Method Reference
To sort students by year, we need a Comparator. Java lets you write one in increasingly short ways. The long form is an anonymous object, with a compare method that calls Integer compare on the two years. A lambda keeps only the parameters and the body. Read it as: given two students, x and y, compare their years. Shortest of all, comparing int with a method reference says it directly: compare by year. Comparing, and comparing double, build Comparators the same way. All three produce the same order: Dee, Ben, Ava, Fay, Cy, Eli.
Multi-Field Order
Chaining Comparators Field by Field
Several students share a year, and several share a GPA. Say we want year first, then GPA from highest to lowest, then name. Comparing int starts the chain. Then comparing adds the next field, here with reverse order for that one key only. The first field that differs decides. Later fields only break ties. The result: Dee and Ben in year one, then Ava, Fay and Cy, then Eli. Careful with reversed at the end of a chain: it flips everything built so far. Here it reversed the year too, putting Eli first. And Collections.reverseOrder, used as a Comparator, sorts the natural order backwards: Fay, Eli, Dee, Cy, Ben, Ava.
Common Mistake
Subtraction Comparators Overflow
Two pitfalls of hand-written comparators. First, it's tempting to compare numbers by subtracting them. That works, until the subtraction overflows. The smallest int, minus one, isn't negative. It wraps around to the largest int, 2,147,483,647. So the subtraction comparator judges the smallest value larger than one, and puts it last. Integer compare puts it first, where it belongs.
Common Mistake
Lambda Types Lost With Reversed
Second, the compiler can't always guess a lambda's type. This line looks harmless. But with reversed on the end, Java can't work out that s is a Student. It treats s as an Object, and reports cannot find symbol. Use the method reference, Student colon colon get GPA, and it compiles. Naming the type inside the lambda works too.
Stability
Ties Keep Their Original Order
A sort is stable if elements that compare as equal keep the relative order they had before. Java's sorts for lists of objects are documented as stable. Sort the starting list by GPA, highest first. Every student ties with two others. The three point eights come out Dee, Ava, Fay: their original order. And the three point fives, Eli, Ben, Cy. Stability lets you build a multi-field order from separate sorts. Sort by the least important field first, then by the most important. Pass one sorts by name, pass two by year. In year two, Ava, Cy and Fay are still alphabetical, though pass two never looked at names. A single chained Comparator is still preferred, because it sorts once. But this is how a spreadsheet's sort-by-column buttons behave.
Related Tools
Reversing Is Not Sorting
Two other tools rearrange a list without comparing anything. Collections.reverse flips the list end to end. It isn't a sort. On the starting list, it gives Cy, Fay, Ben, Ava, Eli, Dee, which is no useful order. Even on a sorted list, the two routes to a descending order aren't identical when there are ties. Sorting descending directly keeps each tie in its original order: Dee, Ava, Fay. Sorting ascending, then reversing, flips every tie too: Fay, Ava, Dee.
Related Tools
Seeded Shuffles and Reversed Views
Collections.shuffle puts elements in a random order: useful for dealing cards, or mixing quiz questions. Two unseeded runs give different results. For a result you can repeat, pass a Random with a fixed seed. Seed forty-two gives three, seven, four, two, five, one, eight, six, every time. Seed seven gives a different order, but one that's just as repeatable. That's what tests and demonstrations need. And from Java twenty-one, every list has a reversed method. It returns a reversed view, without touching the list. The view stays linked. Add four to the original, and the view shows four, three, two, one. Add zero to the view, and it lands at the front of the original.
Quick Check
Sort by Length, Then Reverse
Quick check. Five words, pear, fig, plum, kiwi and yam, are sorted by length, shortest first. Then the list is reversed, and printed. What order comes out? Pause, and predict. Kiwi, plum, pear, yam, fig. The stable sort gave fig and yam, then pear, plum and kiwi, each tie in its original order. Then reverse flipped the whole list, ties included. Pear, plum, kiwi first is what a descending sort would give, keeping each tie. And fig, yam first would mean reverse changed nothing, but it works in place.
Key Takeaways
Comparisons, Sorts and Stability
To sum up. Comparable gives a type one natural order. A Comparator supplies any other order, from outside. A comparison's sign is the answer. List.sort and Collections.sort work in place, and return nothing. Chain fields with comparing and then comparing: the first field that differs decides. Library sorts are stable, so ties keep their order. Reverse flips, shuffle scrambles, and neither one is a sort.
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
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 UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks 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 Rearranging Positional Collections into Order
What is the difference between Comparable and Comparator in Java?
Why should you not compare ints by subtraction in a Comparator?
How do you sort a Java list by multiple fields?
What does it mean that Java's list sort is stable?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
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.
3 credits · NCCRSEnroll →