Ordering of compound objects

We hope you've already got the idea of ordering a sequence of primitive elements like numbers or strings. Sometimes, when the data is more complicated, we should order compound objects that can contain primitives and other objects. Do we have rules to order such data?

Homogeneous sequences

You have two primitives: number 24 and string twenty-four. Which one is greater than the other? Is it even possible to compare numbers with strings at all?

Strings and numbers have a different kind of nature, but we can order only those sequences that consist of homogeneous objects, e.g. having the same type. We can compare strings with strings, but not strings with numbers. In this topic, we review only the ordering of homogeneous objects.

Ordering rows in a table

A table is a format to represent the homogeneous data with multi-value records. Each row in a table has the defined number of columns, and each column contains values with the same type, so it's possible to order those rows.

Let's look at the result of top 3 teams participating in soccer competition where a team gets 3 points for a win, 1 point for a draw, and doesn't get any for loss:

Looking at the table with the final result, how can we order the rows in it when every team gets the same score with 100 points? The simple rule is: we compare rows column by column from left to right. When two values in the same column differ, the order of rows matches the order of these values.

Let's compare the first and the second row:

1. Both rows have the same value 100 in the first column, so we can't order them by these values.
2. In the next column, the first row has value 30, and the second has 25, so the first row should stay before the second as we keep the reverse order.

Comparing the first and the third rows, we can see that it's necessary to change their order because 33 wins are greater than 30 wins, so we conclude that the team with 33 wins is the leader.

Ordering objects

As there is no common rule to order the objects at all, sometimes we can represent objects in a table format too. How can you order 10 cats? It depends on what attributes you would use to compare one cat with another.

We understand that we can still order objects, although it depends on some conditions. To order objects, we can use comparison functions. A comparison function takes two objects as arguments and returns the answer about which one is less than the other.

We can define numerous functions to compare two cats. The function can compare cats by the age, or by the length of a tail, or by any other parameters. With the help of sorting algorithms, this function is all we need to order the cats.

Partial order

In this section, let's look at three geometric figures and compare them by the function: if we can place an object inside the other, this object is less than the object it's compared with.

By the glimpse, we can say that the circle and the triangle are less than the square, but we can't define the order between circle and triangle. Some functions give us only a partial order.

We say that the sequence has a partial order with the relation less or equal when for each $a$, $b$, $c$ from this sequence is true:

• $a \leq a$
• if $a \leq b$ and $b \leq a$ then $a = b$
• if $a \leq b$ and $b \leq c$ then $a \leq c$

Here is the main difference between the total order and the partial order: the total order guarantees comparing objects pairwise, so we can always tell which one is less or equal than the other. On the contrary, in the partial order, some objects are equivalent, and we can't order them linearly.

Conclusion

In this topic, we have dived deeper into comparing different objects. We have also defined the total order for rows in a table, as well as comparison functions to order any other objects. Sometimes comparison functions can give us only the partial order for a sequence. Do not confuse the total order with the partial order and remember that the one is linear and the other is not.