Java Collections Framework: ArrayList and Collections.sort

Sorting WordData objects by frequency in descending order means placing the record with the highest count first.

Programming

Why Word Counts Need an Order

A word-counting program produces one record per distinct word, and each record holds that word's frequency. On its own, that collection of records is only a pile of counts. It becomes useful once the records can be ordered. The most common question people ask about a text is which words appear most often, so the records need to be arranged by their frequency attribute, with the highest count first.

This article focuses on one step: the line that sorts WordData objects in descending order by their count. Before you read the mechanism, commit to a prediction. The sample data holds three records. The word with has a count of 3, the word is has a count of 7, and the word code has a count of 5. Using the rule that the highest count comes first, decide which word should print first and which should print last.

What do you think happens?

Given counts with 3, is 7, and code 5, which word should print first in descending-frequency order?

with
is
code

Reveal answer

Answer:

The count 7 is the highest of the three counts, so the record for is belongs at the front of a descending list. The list then continues with code (count 5) and ends with with (count 3).

Tracing the Records Before and After the Sort

The central statement of the source does three jobs. It copies the values of the words collection into an ArrayList, which gives the program a list it can reorder. It then calls Collections.sort on that list. It also passes a lambda expression as the second argument, and that lambda tells the sort how to compare two WordData objects. Read the statement as a whole first, and then look at each of its parts.

The list starts in the order the records were collected. Suppose the copied list holds with (count 3), then is (count 7), then code (count 5). The sort changes only the order of the entries in the list. Each WordData object keeps its word and its count. What changes is the position each object occupies once the sort finishes.

Which record moves to each position when the list is sorted by count in descending order?

The before and after lists contain exactly the same three objects. Only their positions differ. This is the key idea behind the diagram: the sort reorders references to the records, and the records themselves are not rebuilt.

Reading the Comparator Lambda

The sort needs a rule for deciding whether one WordData object belongs before or after another. The lambda expression (a,b) -> b.count - a.count supplies that rule. The two parameters a and b stand for two WordData objects that the sort wants to compare. The body reads the count attribute of each object and subtracts a's count from b's count.

A comparator returns a number for each pair it is given. A positive result tells the sort that a belongs after b. A negative result tells the sort that a belongs before b. Because the lambda computes b.count minus a.count, the result depends only on the two counts, and the sign of that difference decides the relative order.

For a pair where a has count 3 and b has count 7, what does each subtraction return, and where does that place a relative to b?

Read the diagram as a pair of rules that produce opposite outcomes for the same two records. The descending lambda in the source produces the first column, where a higher count in b makes the result positive and places a after b, so the higher count ends up in front.

java

Collections.sort(wordsByFrequency, (a, b) -> b.count - a.count);

Collections.sort(wordsByFrequency, (a, b) -> b.count - a.count);

Notes on the code

Collections.sort reorders the list it receives
wordsByFrequency is the ArrayList built from the words values
(a, b) are two WordData objects the sort wants to compare
b.count - a.count is the rule that decides their order

EASY

A friend says the lambda (a,b) -> b.count - a.count sorts from lowest count to highest. Using the pair with count 3 and count 7, explain whether your friend is right, showing the value the lambda returns and what that value tells the sort.

Hints

Substitute a.count = 3 and b.count = 7 into b.count - a.count.
Ask which object the sort places first when the result is positive.

Your attempt (not saved)

Tracing Comparator Calls on Pairs

The sort repeats the comparator's decision for many pairs while it reorders the list, so the final order reflects that rule applied across all of them. The source does not describe the internal algorithm Collections.sort uses, so the way to check its behavior is to trace the comparator on individual pairs and then compare the list before and after the call.

For each pair the sort compares, which two WordData objects are involved, what does the comparator return, and does that place the first object before or after the second?

Worked example

Finding where a sorted list diverges from the expected order

A developer expects the descending order is, code, with. The developer changes the lambda to (a,b) -> a.count - b.count and runs the sort on the same three records. Trace the comparator on the pair with and is to find where the result stops matching the expectation.

1
Identify the pair
Let a be with (count 3) and b be is (count 7).
2
Evaluate the changed comparator
a.count - b.count gives 3 minus 7, which is minus 4. A negative result places a before b, so with is placed ahead of is.
3
Compare with the expected order
The expected descending order puts is first. The changed comparator has put with ahead of is, so the first difference appears at this pair.
4
Confirm the cause
The sign of the comparator's result was reversed by swapping the operands. The copy into the ArrayList and the call to Collections.sort were not the source of the mismatch.

Result

The divergence is caused by the comparator's operand order. The list ends up in ascending order, with with first and is last, because the subtraction was reversed.

Mistakes That Break the Frequency Order

Common mistake
Swapping the comparator operands
What it looks like
```
(a,b) -> a.count - b.count
```
Why it fails
The source states that writing b first produces a descending order. Reversing the subtraction flips the sign of every comparison and produces an ascending order instead.
Do this instead
Keep b.count - a.count when the highest count should come first.
Common mistake
Comparing the wrong attribute
What it looks like
```
(a,b) -> b.word - a.word
```
Why it fails
The sort orders by the frequency attribute named count, so comparing another field changes the meaning of the order.
Do this instead
Read the body of the lambda and confirm it reads count from both parameters.
Common mistake
Expecting the Map itself to be reordered
Why it fails
The source explains that a sort cannot change a Map directly in the way a list can be reordered, so the values are copied into an ArrayList first.
Do this instead
Copy words.values() into an ArrayList, then sort that list with the comparator.
Common mistake
Forgetting that the sort changes only positions, not the WordData objects themselves

Predict and Check the Order

MEDIUM

Three WordData records are stored in an ArrayList in this order: code (count 5), with (count 3), is (count 7). Predict the list after Collections.sort(list, (a,b) -> b.count - a.count). Then state the comparator result for the pair code and with, and say whether code is placed before or after with.