> For the complete documentation index, see [llms.txt](https://strctr.gitbook.io/programming/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://strctr.gitbook.io/programming/01-languages/scala/01-scala-language/scala-ordering.md).

# Ordering

## Ordering in Scala

Ordering in scala implemended with following types located at `scala.math`:

* `Ordering[T]` - trait whose instances each represent a strategy for sorting instances of a type.
* `PartialOrdering[T]` - representation of partial ordering on some type.
* `Equiv[T]` - representation of equivalence on some type.
* `Ordered[T]` - trait for data that have a single, natural ordering.
* `Ordering.Implicits` - access to other implicit orderings.

### Ordering

`Ordering` is a trait whose instances each represent a strategy for sorting instances of a type. An `Ordering[T]` is implemented by specifying `compare(a:T, b:T)`, which decides how to order two instances `a` and `b`. Ordering has the same purpose as `Comparator` in Java, but with scala extensions, implicit and related math properties.

Most sorting functionality implemented in the scala library operates using instances of `Ordering`, so usage of sorting is a preferable way to implement order relation in scala. Providing an ordering directly eliminates an implicit conversion in most cases.

Instances of `Ordering[T]` can be used by things like `scala.util.Sorting` to sort collections like `Array[T]`.

```scala
import scala.util.Sorting

case class Person(name:String, age:Int)
val people = Array(Person("bob", 30), Person("ann", 32), Person("carl", 19))

// sort by age
object AgeOrdering extends Ordering[Person] {
  def compare(a:Person, b:Person) = a.age compare b.age
}
Sorting.quickSort(people)(AgeOrdering)
```

### Ordering companion object

Ordering's companion object defines many implicit objects to deal with subtypes of `AnyVal` (e.g. `Int`, `Double`), `String`, and others.

* `Ordering.by`
* `Ordering.on`

```scala
case class Employee(id: Int, firstName: String, lastName: String)

object Employee {
  // Note that because `Ordering[A]` is not contravariant, the declaration
  // must be type-parametrized in the event that you want the implicit
  // ordering to apply to subclasses of `Employee`.
  implicit def orderingByName[A <: Employee]: Ordering[A] =
    Ordering.by(e => (e.lastName, e.firstName))

  val orderingById: Ordering[Employee] = Ordering.by(e => e.id)
}
```

Given `es: SeqLike[Employee]`, `es.sorted()` will sort by name, and `es.sorted(Employee.orderingById)` will sort by `id`.

For case classes ordering on deconstruction can be used:

```scala
object A {
  implicit val ord = Ordering.by(unapply)
}
```

This has the benefit that it is updated automatically whenever `A` changes. But, `A`'s fields need to be placed in the order by which the ordering will use them.

### Ordered

Trait `Ordered` is the analogue of `Comparable` in Java. Classes that implement `Ordered` trait can be sorted with `scala.util.Sorting` and can be compared with standard comparison operators (e.g. > and <). `Ordered` and `Ordering` both provide implicits allowing them to be used interchangeably.

```scala
case class A(tag: String, load: Int) extends Ordered[A] {
  // Required as of Scala 2.11 for reasons unknown - the companion to Ordered
  // should already be in implicit scope
  import scala.math.Ordered.orderingToOrdered

  def compare(that: A): Int = (this.tag, this.load) compare (that.tag, that.load)
}
```

Note that `Ordering` and `Ordered` does not provide implementation of `equals` methods. Developers must implement this method by itself and make sure that it consistent with ordering.

### Extra Implicits

This works: why??

```
import scala.math.Ordering.Implicits._
var x = (1,2,3) < (1,2,4)
```

#### Partial Ordering

Partial Ordering trait defines only one method `def lteq(x: T, y: T): Boolean` which returns `true` iff `x` comes before `y` in the ordering.

A partial ordering is a binary relation on a type `T`, exposed as the `lteq` method of this trait. This relation must be: *reflexive*: `lteq(x, x) == true`, for any `x` of type `T`. *anti-symmetric*: if `lteq(x, y) == true` and `lteq(y, x) == true` then `equiv(x, y) == true`, for any x and y of type T. *transitive*: if `lteq(x, y) == true` and `lteq(y, z) == true` then `lteq(x, z) == true`, for any `x`, `y`, and `z` of type `T`.

Additionally, a partial ordering induces an *equivalence relation* on a type `T`: `x` and `y` of type `T` are equivalent if and only if `lteq(x, y) && lteq(y, x) == true`.

#### Equivalence relation

An equivalence relation is a binary relation on a type. This relation is exposed as the `equiv` method of the `Equiv` trait. The relation must be: *reflexive*: `equiv(x, x) == true` for any `x` of type `T`. *symmetric*: `equiv(x, y) == equiv(y, x)` for any `x` and `y` of type `T`. *transitive*: if `equiv(x, y) == true` and `equiv(y, z) == true`, then `equiv(x, z) == true` for any `x`, `y`, and `z`s of type `T`.

## Sorting in Scala

Sorting in scala implemented in `scala.util.Sorting` object.&#x20;

Вопросы:

* Какие типы отвечают за упорядочивание в scala?
* Как работает trait `Ordering`, какие у него возможности.
* Способы применения `Ordering`.
* В чем отличие `Ordered` от `Ordering`.
* Как подключить реализованные неявные Ordering для разных типов данных?
* Как задать частичный порядок на типе T?
* Какие свойства частичного порядка есть?
* Как задать отношение эквивалентности на типе T. Какими свойствами должно обладать отношение эквивалентности.
* Как реализована сортировка в Scala.