Collection processing in Kotlin: Sorting, shuffling and reversing

This is a chapter from the book Functional Kotlin. You can find it on LeanPub or Amazon. It is also available as a course.

To have your collection elements organized in a concrete order, we can use sorting functions: sorted, sortedBy and sortedWith.

sorted can only be used on a list of elements with natural order for elements that implement the Comparable interface. The most important types with natural order are:

Int, Long, Double and other basic classes representing numbers that are sorted from the lowest number to the highest.

Char is treated as a number in UTF-16 code under the hood, so comparing two characters is like comparing their codes. Letters are organized in alphabetical order, but all capital letters come before all lowercase letters. A space comes before all letters.

String, whose natural order is lexicographical (this is a generalization of the alphabetical order that is used in dictionaries), where we start from comparing the first character (according to Char order); whenever two characters are equal, we are shifting the burden of the decision to the next character.

Boolean places false before true. This is because false and true are typically represented by 0 and 1, respectively, and the natural order for numbers places 0 before 1.

fun main() { println(listOf(4, 1, 3, 2).sorted()) // [1, 2, 3, 4] println(listOf('b', 'A', 'a', ' ', 'B').sorted()) // [ , A, B, a, b] println(listOf("Bab", "AAZ", "Bza", "A").sorted()) // [A, AAZ, Bab, Bza] println(listOf(true, false, true).sorted()) // [false, true, true] }

To reverse the order of the elements in the list, use the reversed method.

fun main() { println(listOf(4, 1, 3, 2).reversed()) // [2, 3, 1, 4] println(listOf('C', 'B', 'F', 'A', 'D', 'E').reversed()) // [E, D, A, F, B, C] }

To reverse the sorting order, we can use the sortedDescending function, which gives the same result as first using sorted and then reversed.

fun main() { println(listOf(4, 1, 3, 2).sortedDescending()) // [4, 3, 2, 1] println(listOf(4, 1, 3, 2).sorted().reversed()) // [4, 3, 2, 1] println( listOf('b', 'A', 'a', ' ', 'B') .sortedDescending() ) // [b, a, B, A, ] println( listOf("Bab", "AAZ", "Bza", "A") .sortedDescending() ) // [Bza, Bab, AAZ, A] println(listOf(true, false, true).sortedDescending()) // [true, true, false] }

If we want to sort elements by one of their properties, we should use sortedBy, which sorts elements by the value its selector returns. For instance, if we have a list of students and we want to sort them by the semester, we can use sortedBy with a selector that reads the semester value.

// Sort students by the semester students.sortedBy { it.semester } // Sort students by surname students.sortedBy { it.surname }

In other words, in sortedBy, the selector decides what value should be compared when we sort elements. This value needs to be comparable to instances of the same type (implement Comparable<T> interface).

fun main() { val names = listOf("Alex", "Bob", "Celine") // Sort by name length println(names.sortedBy { it.length }) // [Bob, Alex, Celine] // Sort by last letter println(names.sortedBy { it.last() }) // [Bob, Celine, Alex] }

All Kotlin standard library sorting functions are implemented in such a way, so that equal elements remain in the same order (so we say that a stable sorting algorithm is being used).

fun main() { val names = listOf("Ben", "Bob", "Bass", "Alex") val sorted = names.sortedBy { it.first() } println(sorted) // [Alex, Ben, Bob, Bass] }

sortedBy also has a descending alternative called sortedByDescending.

fun main() { val names = listOf("Alex", "Bob", "Celine") // Sort by name length println(names.sortedByDescending { it.length }) // [Celine, Alex, Bob] // Sort by last letter println(names.sortedByDescending { it.last() }) // [Alex, Celine, Bob] }

We might use sortedBy or sortedByDescending to sort users by their login, news by publication date, or tasks by priority.

// Users sorted by login val usersSorted = users .sortedBy { it.login } // News sorted starting from the newest val newsFromLatest = news .sortedByDescending { it.publicationDate } // News sorted starting from the oldest val newsFromOldest = news .sortedBy { it.publicationDate } // Tasks from the highest priority to the lowest val tasksInOrder = tasks .sortedByDescending { it.priority }

The selectors of sortedBy and sortedByDescending accept null, which is considered less than all other values.

fun main() { val people = listOf( Person(1, "Alex"), Person(null, "Ben"), Person(2, null), ) println(people.sortedBy { it.id }) // [null: Ben, 1: Alex, 2: null] println(people.sortedBy { it.name }) // [2: null, 1: Alex, null: Ben] }

It gets more complicated when we need to sort by more than one property. For example, a typical governmental order of people’s names requires sorting them by their surnames, and then people with the same surnames should be sorted by their first names. How can we implement this? Sorting by name first and then by surname would give us the correct result, but would be terribly inefficient. A much better solution is using sortedWith.

sortedWith is a function that returns a collection sorted according to a comparator it receives as an argument. The comparator is an object that implements the Comparator interface.

fun interface Comparator<T> { fun compare(a: T, b: T): Int }

In many languages, it is popular to make an object that implements a comparator.

names.sortedWith(Comparator { o1, o2 -> when { o1.surname < o2.surname -> -1 o1.surname > o2.surname -> 1 o1.name < o2.name -> -1 o1.name > o2.name -> 1 else -> 0 } })

We can do that in Kotlin too, but in most cases it is better to use one of the top-level functions from the standard library. For instance, we can use compareBy to create a comparator that first compares using one selector; then, if it considers two objects equal, it compares values using the next selector. This way, we can make a comparator with multiple sorting selectors, used lexicographically.

data class FullName(val name: String, val surname: String) { override fun toString(): String = "$name $surname" } fun main() { val names = listOf( FullName("B", "B"), FullName("B", "A"), FullName("A", "A"), FullName("A", "B"), ) println(names.sortedBy { it.name }) // [A A, A B, B B, B A] println(names.sortedBy { it.surname }) // [B A, A A, B B, A B] println(names.sortedWith(compareBy( { it.surname }, { it.name } ))) // [A A, B A, A B, B B] println(names.sortedWith(compareBy( { it.name }, { it.surname } ))) // [A A, A B, B A, B B] }

sortedBy(selector) under the hood is just sortedWith(compareBy(selector)).

sortedWith and compareBy can be used for as many selectors as we want, which makes them really universal for complex sorting.

return recommendations.sortedWith( compareBy( { it.blocked }, // blocked to the end { !it.favourite }, // favorite at the beginning { calculateScore(it) }, ) )

When we need to construct a more complex comparator, we have a variety of standard library functions. We can create a new comparator using:

compareBy,

naturalOrder (sorts with natural order),

reverseOrder (sorts with the reverse of natural order),

nullsFirst and nullsLast (both use natural order, but they also place nulls first or last).

Then, when we have a comparator, we can modify it using functions on Comparator, such as:

then or thenComparator, both of which add another comparator that is used when the previous comparator considers elements equal;

thenBy, which compares values using a selector when the previous comparator considers elements equal;

reversed, which reverses the comparator order.

class Student( val name: String, val surname: String, val score: Double, val year: Int, ) { companion object { val ALPHABETICAL_ORDER = compareBy<Student>({ it.surname }, { it.name }) val BY_SCORE_ORDER = compareByDescending<Student> { it.score } val BY_YEAR_ORDER = compareByDescending<Student> { it.year } } } fun presentStudentsForYearBook() = students .sortedWith( Student.BY_YEAR_ORDER.then(Student.ALPHABETICAL_ORDER) ) fun presentStudentsForTopScores() = students .sortedWith( Student.BY_YEAR_ORDER.then(Student.BY_SCORE_ORDER) )

Sorting mutable collections

If you want to sort a mutable collection, you can use the sort function. This is a part of classic collection processing as it modifies a mutable list instead of returning a processed one. The sort method is often confused with sorted. The sort method is an extension function on MutableList that, in contrast to sorted, sorts a list and returns Unit. The sorted method is an extension function on Iterable that does not modify its receiver and returns a sorted collection.

fun main() { val list = listOf(4, 2, 3, 1) val sortedRes = list.sorted() // list.sort() is illegal println(list) // [4, 2, 3, 1] println(sortedRes) // [1, 2, 3, 4] val mutableList = mutableListOf(4, 2, 3, 1) val sortRes = mutableList.sort() println(mutableList) // [1, 2, 3, 4] println(sortRes) // kotlin.Unit }

There are also sortBy, sortByDescending and sortWith, which respectively work similarly to sortedBy, sortedByDescending and sortedWith, but they modify a mutable collection instead of returning a new one.

Maximum and minimum

Another common situation is that we need to find extremes in a collection: the biggest or the smallest element. We could first sort the elements and then take the first or the last one, but such a solution would be far from optimal. Instead, we should use functions that start with the "max" or "min" prefix.

If we want to find an extreme using the natural order of the elements, use maxOrNull or minOrNull, both of which return null when a collection is empty.

fun main() { val numbers = listOf(1, 6, 2, 4, 7, 1) println(numbers.maxOrNull()) // 7 println(numbers.minOrNull()) // 1 }

If we want to find an extreme according to a selector (similar to sortedBy), use maxByOrNull or minByOrNull.

data class Player(val name: String, val score: Int) fun main() { val players = listOf( Player("Jake", 234), Player("Megan", 567), Player("Beth", 123), ) println(players.maxByOrNull { it.score }) // Player(name=Megan, score=567) println(players.minByOrNull { it.score }) // Player(name=Beth, score=123) }

You can also find an extreme according to a comparator. In such a case, use maxWithOrNull or minWithOrNull.

data class FullName(val name: String, val surname: String) fun main() { val names = listOf( FullName("B", "B"), FullName("B", "A"), FullName("A", "A"), FullName("A", "B"), ) println( names .maxWithOrNull(compareBy( { it.surname }, { it.name } )) ) // FullName(name=B, surname=B) println( names .minWithOrNull(compareBy( { it.surname }, { it.name } )) ) // FullName(name=A, surname=A) }

Another case is when you want to find an extreme value of a property: not the element that contains the extreme value but the value itself. For example, you have a list of students and you want to find their highest score. You could map the students to scores and then find the maximal value, or you could find the student with the highest score and get this score. However, both of these options do a lot of unnecessary operations. Instead, we should use the maxOfOrNull or minOfOrNull method with a selector that extracts a score (or maxOf/minOf if you are sure that your collection is not empty).

data class Player(val name: String, val score: Int) fun main() { val players = listOf( Player("Jake", 234), Player("Megan", 567), Player("Beth", 123), ) println(players.map { it.score }.maxOrNull()) // 567 println(players.maxByOrNull { it.score }?.score) // 567 println(players.maxOfOrNull { it.score }) // 567 println(players.maxOf { it.score }) // 567 println(players.map { it.score }.minOrNull()) // 123 println(players.minByOrNull { it.score }?.score) // 123 println(players.minOfOrNull { it.score }) // 123 println(players.minOf { it.score }) // 123 }

`shuffled` and `random`

We have learned how to sort elements, but we might also want to shuffle them. To get a random number from a collection, use random (or randomOrNull for possibly empty lists). To shuffle an iterable (to make its order random), use shuffled. For these functions, you can pass a custom Random object as an argument.

import kotlin.random.Random fun main() { val range = (1..100) val list = range.toList() // `random` requires a collection println(list.random()) // random number from 1 to 100 println(list.randomOrNull()) // random number from 1 to 100 println(list.random(Random(123))) // 7 println(list.randomOrNull(Random(123))) // 7 println(range.shuffled()) // List with numbers in a random order }

data class Character(val name: String, val surname: String) fun main() { val characters = listOf( Character("Tamara", "Kurczak"), Character("Earl", "Gey"), Character("Ryba", "Luna"), Character("Cookie", "DePies"), ) println(characters.random()) // A random character, // like Character(name=Ryba, surname=Luna) println(characters.shuffled()) // List with characters in a random order }