检查 Scala 集合是否已排序

1. Introduction

In this tutorial, we’ll look into different ways to check if a collection is sorted in Scala.

Generally, sorting a collection has the complexity of O(n log n) or even worse. Moreover, in certain situations such as binary searching, the task requires the collection to be sorted. In such cases, it’s good to check if the collection is sorted before proceeding with further operations.

2. Setup

All the implementations in this tutorial use an input to define if the expected order is ascending or descending. To do that, let’s define an enum:

enum Direction:
  case ASC, DESC

We’ll use this enum to decide the method to be used for the comparison.

Furthermore, we’ll use a generic implementation for all types that provide an Ordering instance. This way, the implementation works for types such as Int, Long, String, and any other types that can provide an Ordering type-class instance.

3. Using sorted()

The easiest and straight-forward way to check if a collection is sorted is by comparing it against the sorted list:

def isSortedBySorting[A](list: List[A], direction: Direction)(using
  ord: Ordering[A]
): Boolean = {
  direction match {
    case Direction.ASC  => list.sorted == list
    case Direction.DESC => list.sorted.reverse == list
  }
}

Depending on the direction provided, this implementation compares the input with the sorted collection of the input list. However, this approach is inefficient as sorting is an expensive operation, especially on larger inputs. Moreover, it defeats the purpose of checking if the collection is sorted by sorting the entire collection.

4. Using sliding()

We can use sliding() method to group elements into a group of two and compare if they’re in the correct order. Similar to the previous case, we’ll use a direction parameter to specify if we should check for ascending or descending order:

def isSortedBySliding[A](list: List[A], direction: Direction)(using
  ord: Ordering[A]
): Boolean = {
  val comparator = if (direction == ASC) ord.lteq else ord.gteq
  list match {
    case Nil | _ :: Nil => true
    case _ => list.sliding(2).forall { case List(a, b) => comparator(a, b) }
  }
}

*As we utilize forall(), the algorithm exits immediately upon detecting the first mismatch, thereby avoiding the need to compare additional elements*. Additionally, if the list is empty or contains only one element, we immediately return the result as true.

5. Using Tail Recursion

We can use tail recursion to compare each element of a list to check if the collection is sorted. Let’s look at the implementation:

@tailrec
def isSortedRecursive[A](list: List[A], direction: Direction)(using
  ord: Ordering[A]
): Boolean = {
  val comparator = if (direction == ASC) ord.lteq else ord.gteq
  list match {
    case Nil | _ :: Nil => true
    case a :: b :: tail =>
      comparator(a, b) && isSortedRecursive(b :: tail, direction)
  }
}

Here, we use pattern matching to extract the initial two elements from the list and check if they are in the correct order. Subsequently, we recursively invoke the method to compare the remaining elements.

6. Using zip()

Another way to check if a collection is sorted is by using the zip() method:

def isSortedByZip[A](list: List[A], direction: Direction)(using
  ord: Ordering[A]
): Boolean = {
  val comparator = if (direction == ASC) ord.lteq else ord.gteq
  if (list.size < 2)
    true
  else
    list.zip(list.tail).forall { case (a, b) => comparator(a, b) }
}

Here, we zip the list with its tail. The tail() operation, when applied to a list, generates a new list by excluding the initial element. Applying the zip() operation on this tail produces a list of tuples, each comprising two consecutive elements from the original list. We can effectively determine whether the order is preserved by comparing these elements.

7. Using lazyZip()

Instead of zip(), we can use the lazyZip() method to improve the efficiency of the implementation:

def isSortedByLazyZip[A](list: List[A], direction: Direction)(using
  ord: Ordering[A]
): Boolean = {
  val comparator = if (direction == ASC) ord.lteq else ord.gteq
  if (list.size < 2)
    true
  else
    list.lazyZip(list.tail).forall { case (a, b) => comparator(a, b) }
}

This implementation is very similar to the previous implementation except for the usage of lazyZip() instead of zip(). While the zip() method eagerly creates the tuples from the input, lazyZip() constructs them on demand. This approach avoids unnecessary tuple creation, resulting in enhanced performance, particularly when dealing with extensive datasets.

8. Conclusion

In this article, we looked at different methods to check if a collection is sorted. The lazyZip() approach is particularly beneficial for large collections where performance optimization is crucial while other approaches like tail recursion and sliding() offer efficient alternatives for checking if a collection is sorted.

As always, the sample code used in this tutorial is available over on GitHub.

Persistence

REST

Security