Sorting Techniques in Scala: An Introduction | CodeSignal Learn

Sorting Techniques in Scala: An Introduction | CodeSignal Learn

Lesson Introduction and Overview

Hello, and welcome back! Our journey today takes us into the sorting universe in Scala . We will learn about and utilize Scala's built-in sorting methods, such as sorted for sequences and lists. These tools in Scala significantly simplify the task of sorting. Let's get started!

Understanding Sorting and Its Importance

Sorting refers to arranging data in a specific order, which enhances the efficiency of search or merge operations on data. In real life, we sort books alphabetically or clothes by size. Similar concepts are applicable in programming, where sorting large lists of data for more effective analysis is a frequent practice. Scala, with its immutable collections and functional programming paradigm, offers efficient sorting methods. You can use the sorted method available on sequences and lists to achieve this.

Sorting of Primitive Types and Objects

Sorting with Scala's sorted method makes sorting collections of primitives a breeze. Let's see it in action! Sorting Lists of Primitives Scala val arr = List(4, 1, 3, 2) val sortedArr = arr.sorted println(sortedArr.mkString(", ")) // Output: 1, 2, 3, 4 Sorting Lists of Strings Scala val inventory = List("Bananas", "Pears", "Apples", "Dates") val sortedInventory = inventory.sorted sortedInventory.foreach(println) // Output: // Apples // Bananas // Dates // Pears As you can see, sorting in Scala is as simple as that!

More Complex Sorting Problem

Scala allows us to define custom sorting logic for multi-key sorting. Let's sort a list of students by their grades in descending order, with alphabetical sorting applied in the event of ties in grades: Scala case class Student(name: String, grade: Int) val students = List(Student("Alice", 85), Student("Bob", 90), Student("Charlie", 90))

Ad-Hoc Pattern: Negation for Reverse Order

A common but non-idiomatic approach is to negate numeric values to achieve descending order: Scala val sortedStudents = students.sortBy(s => (-s.grade, s.name)) println(sortedStudents.mkString(", ")) // Output: Student(Bob,90), Student(Charlie,90), Student(Alice,85) In this pattern, we use -s.grade with a negative sign to achieve descending order for grades. This works because negating the values inverts the natural ordering: larger grades become smaller negative numbers, which then sort first. The s.name field has no negative sign, so names are sorted in ascending (alphabetical) order when grades are equal. Limitations of this approach: Only works for numeric types Can cause overflow issues with extreme values Not immediately clear to readers unfamiliar with this pattern Cannot reverse strings or other non-numeric types

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Idiomatic Pattern: Ordering Combinators

The idiomatic Scala approach uses Ordering combinators to compose sort keys with explicit directions: val idiomaticSortedStudents = students.sortBy(s => (s.grade, s.name))(Ordering.Tuple2(Ordering.Int.reverse, Ordering.String)) println(idiomaticSortedStudents.mkString(", ")) // Output: Student(Bob,90), Student(Charlie,90), Student(Alice,85) Here's what makes this approach superior: Explicit : The .reverse clearly indicates descending order Type-safe : Works with any type that has an Ordering Composable : Easily mix ascending and descending directions Readable : Intent is immediately clear to all readers For three or more keys, use Ordering.Tuple3, Ordering.Tuple4, etc.: case class Employee(name: String, department: String, salary: Int, yearsOfService: Int) val employees = List(Employee("Alice", "Engineering", 90000, 5), Employee("Bob", "Engineering", 90000, 3), Employee("Charlie", "Sales", 85000, 7)) // Sort by: department (asc), salary (desc), years (desc) val sortedEmployees = employees.sortBy(e => (e.department, e.salary, e.yearsOfService))(Ordering.Tuple3(Ordering.String, Ordering.Int.reverse, Ordering.Int.reverse)) sortedEmployees.foreach(println) // Output: // Employee(Alice,Engineering,90000,5) // Employee(Bob,Engineering,90000,3) // Employee(Charlie,Sales,85000,7)

Scala

val idiomaticSortedStudents = students.sortBy(s => (s.grade, s.name))(
  Ordering.Tuple2(Ordering.Int.reverse, Ordering.String)
)
println(idiomaticSortedStudents.mkString(", ")) // Output: Student(Bob,90), Student(Charlie,90), Student(Alice,85)

Scala

case class Employee(name: String, department: String, salary: Int, yearsOfService: Int)

val employees = List(
  Employee("Alice", "Engineering", 90000, 5),
  Employee("Bob", "Engineering", 90000, 3),
  Employee("Charlie", "Sales", 85000, 7)
)

// Sort by: department (asc), salary (desc), years (desc)
val sortedEmployees = employees.sortBy(e => (e.department, e.salary, e.yearsOfService))(
  Ordering.Tuple3(Ordering.String, Ordering.Int.reverse, Ordering.Int.reverse)
)

sortedEmployees.foreach(println)
// Output:
// Employee(Alice,Engineering,90000,5)
// Employee(Bob,Engineering,90000,3)
// Employee(Charlie,Sales,85000,7)