# 29.1 The Sorting Problem

## Sorting

For the remaining part of this textbook, we'll discuss the sorting problem, which can be informally defined as putting a given set of items in a particular order.

This is a useful task in its own right, but can also be a subproblem in larger algorithmic problems. Sorting can be applied to problems like duplicate finding (after sorting, equivalent items are adjacent), binary search, and balancing data structures.

The other reason we introduce sorting is that the different sorts provide general ideas about how to approach computational problems. The solution(s) to sorting problems will often involve data structures covered in the earlier parts of this course.

### Sorting: Definitions

An **ordering relation** $$<$$ for keys a, b, and c has the following properties:

* _Law of Trichotomy_: Exactly one of a $$<$$ b, a = b, b $$<$$ a is true.
* _Law of Transitivity_: If a $$<$$ b, and b $$<$$ c, then a $$<$$ c.

An ordering relation with the properties above is also known as a **total order**.&#x20;

A **sort** is a permutation of a sequence of elements that puts the keys into non-decreasing order relative to a given ordering relation, such that x1 ≤ x2 ≤ x3≤ ...≤ xN.

#### Example: String Length

One example of a ordering relation is the length of strings. To see how the two laws apply:

* _trichotomy_: only one of the following can be true for two strings `a` and `b`--`len(a)` < `len(b)`, `len(a)` = `len(b)`, or `len(a)` > `len(b)`.
* _transitivity:_ if `len(a)` < `len(b)` and `len(b)` < `len(c)`, then clearly `len(a)` < `len(c)`.

Suppose we use the ordering relation above to sort `["cows", "get", "going", "the"]`. Then two valid sorts would be `["the", "get", "cows", "going"]` and `["get", "the", "cows", "going"]`. Note that in this sort, `the` and `get` are equivalent since their lengths are equal.

### Ordering Relations in Java

In Java, ordering relations are typically given by the `compareTo` or `compare` methods. For example:

```java
import java.util.Comparator;
 
public class LengthComparator implements Comparator<String> {
    public int compare(String x, String b) {
        return x.length() - b.length();
    }
}
```

Note by the relation above, `the` and `get` are equal in ordering, but _not_ equal by the `.equals()` method.

### Inversions

An alternate way to view sorting is as fixing inversions within a sequence of elements. An **inversion** is a pair of elements that are out of order with respect to the defined ordering relation.

For example, in the following sequence of 11 elements, there are 55 possible inversions at most (11 choose 2), and the sequence itself has 6 inversions.

<figure><img src="https://content.gitbook.com/content/17YWK4wlHXK38A55HuVr/blobs/qf9XtSZV3MdXdatXye2p/image.png" alt=""><figcaption><p>The sequence above has 6 inversions</p></figcaption></figure>

Sorting, then, can be viewed as follows: given a sequence of elements with Z inversions, perform some sequence of operations to reduce the total number of inversions to zero.

### Sorting: Performance

Previously, we have seen characterizations of of the runtime efficiency of an algorithm, also called the **time complexity** of an algorithm. For example, we can say that Dijkstra’s has time complexity O(E log V).

Characterizations of the “extra” memory usage of an algorithm is sometimes called the **space complexity** of an algorithm. For example, Dijkstra’s has space complexity Θ(V) to store the queue, `distTo`, and `edgeTo` arrays. Note that the graph takes up space Θ(V+E), but we don’t count this as part of the space complexity of Dijkstra since the graph is an input to Dijkstra’s. In other words, we are only concerned with the _extra_ space used by the algorithm.
