Sorting a collection
Scala offers two families of sorting methods. One returns a new, sorted collection and leaves the original alone. The other sorts a mutable Array in place. Choosing between them is mostly a question of whether you still need the original order.
sorted works on any collection whose elements have a natural order, such as numbers and strings, and returns a new collection in ascending order:
val numbers = List(5, 2, 11, 7, 3)
val ascending = numbers.sorted // List(2, 3, 5, 7, 11)
val descending = numbers.sorted.reverse // List(11, 7, 5, 3, 2)
After these lines numbers is still List(5, 2, 11, 7, 3). A List is immutable, so it can't be sorted in place anyway.
For another order, sortWith takes a function that receives two elements and returns true when the first must come before the second:
val words = List("pie", "banana", "book")
val byLength = words.sortWith((a, b) => a.length < b.length) // List(pie, book, banana)
When the order depends on one value computed from each element, sortBy is shorter: words.sortBy(_.length) gives the same result. Sorting takes O(n log n) time.
Sorting an array in place
An Array is mutable, and it has methods that rearrange its own elements: sortInPlace() for the natural order and sortInPlaceWith for a custom one. They return nothing useful, so you call them for their effect:
val a = Array(3, 1, 2)
a.sortInPlace()
println(a.mkString(",")) // 1,2,3
println(Array(2, 1, 3, 10).sorted.mkString(",")) // 1,2,3,10
Note that sorted on an array also returns a new array and leaves the original as it was. Printing an array directly with println shows an object reference, not its contents, so the examples here use mkString.
The lesson's exercise, step by step
The exercise sorts three arrays, each in a different way.
Numbers in descending order
First, numbers is declared with val as Array(2, 1, 3, 10). A val fixes which array the name refers to; the elements inside can still change, which is why in-place sorting works on it. Then sortInPlaceWith(_ > _) sorts it. The function _ > _ is shorthand for (a, b) => a > b, and since it returns true when the first argument is larger, larger numbers come first. The array becomes 10, 3, 2, 1.
Pairs by first value, then second value descending
Next, coordinates is an array of three pairs, each itself an Array: Array(3, 2), Array(2, 3) and Array(3, 5). The sort has two rules. Pairs are ordered by their first value ascending, and when two first values are equal, by the second value descending. The comparison function expresses this with an if/else expression:
- If
a(0) == b(0), the first values tie, so the result isb(1) < a(1). Swapping the sides reverses the order, and the pair with the larger second value goes first. - Otherwise the result is
a(0) < b(0), the ordinary ascending comparison.
The result is [2, 3], [3, 5], [3, 2]. Elements are read with parentheses, a(0), not a[0].
Names, ignoring case
Finally, names is Array("Mircea", "john", "Andy"). Strings compare by character code, and every uppercase letter has a smaller code than every lowercase one, so the plain sorted gives Andy, Mircea, john, with john last. To ignore case, compare lowercase copies: names.sortInPlaceWith { (a, b) => a.toLowerCase < b.toLowerCase }. The array becomes Andy, john, Mircea. The original strings keep their capitals, because only the comparison uses the lowercase versions. toLowerCase takes no arguments, so Scala lets you call it without parentheses.
The solution in Scala
val numbers = Array(2, 1, 3, 10)
numbers.sortInPlaceWith(_ > _)
val coordinates = Array(
Array(3, 2),
Array(2, 3),
Array(3, 5)
)
coordinates.sortInPlaceWith { (a, b) =>
if (a(0) == b(0)) {
b(1) < a(1)
} else {
a(0) < b(0)
}
}
val names = Array("Mircea", "john", "Andy")
names.sortInPlaceWith { (a, b) => a.toLowerCase < b.toLowerCase }
Common mistakes
- Expecting
sortedto change the original. It returns a new collection. To keep the sorted array, store it:val sortedNumbers = numbers.sorted. - Using
<=or>=in a comparison function. The function should say whether the first element is strictly before the second. For equal elements it should returnfalse. - Calling
sortInPlaceWithon aList. Lists are immutable and have no in-place methods. UsesortWith, which returns a new list. - Forgetting the tie rule. A comparison that only looks at the first values leaves ties in an unspecified order relative to the second values.
Key takeaways
sorted,sortWithandsortByreturn a new collection;sortInPlaceandsortInPlaceWithrearrange a mutable array.- A
valarray can still be sorted in place, becausevalonly fixes the reference. - A comparison function returns
truewhen its first argument must come first. - Reverse a comparison by swapping its two sides.
- Compare lowercase copies to sort strings without regard to case.
