What's the difference between ordering and sorting?

Question

No, it's not a question from a class, I'm studying trees and heaps ( partially sorted binary tree ) by myself and I was wondering how to correctly define this 2 properties/actions in relation to a generic data structure.

Answer 1

• An "ordering" is basically a set of rules that determine what items come before, or after, what other items. IE: the relative order items would appear in if they were sorted. For collections that enforce an ordering, that ordering is generally specified in terms of comparison operators (particularly <), interfaces (a la Java's Comparable<T>), or comparison callbacks and/or function objects (like C++'s std::less).

  There are also collections described as "ordered collections". Slightly different use of the word, but related meaning. What that means is that the collection represents a sequence of items, and thus has some inbuilt concept of order. (Contrast with, say, hash tables. You add something to a hash table, you have no idea where it'll appear if ever you iterate over the contents. With an ordered collection, you know.) Lists, vectors, arrays, etc are the quintessential ordered collections. For a non-list example, though, PHP's "array" type is actually an "ordered map" — a dictionary type where the order of keys is retained. Keys appear in the order in which they were first inserted (or the order in which you last put them with a ksort() or the like) when you iterate over the array.

• "Sorting" is the process of actually arranging a sequence of items in accordance with a given ordering. It's typically only done with ordered collections...as it doesn't make much sense to put one item before another in a container that has no concept of "before" or won't let you rearrange items in the first place. (Structures like sets and heaps can use an ordering too, and adding and removing entries alters the underlying tree based on the ordering. One could argue they're "sorting" bit by bit. But the word is typically used to represent an operation that does the rearranging all at once.)

Answer 2

Very roughly speaking, an ordering specifies which elements should be ordered before which other elements in some sequence. Sorting is the process of putting a collection of such elements into the order specified by an ordering.

(Slightly confusingly, it's also possible to talk about "ordering" a sequence of elements, which means the same thing as sorting them into some order specified by an ordering.)

---

UPDATE:

In implementation terms, a good example would be the standard containers (e.g. map, http://en.cppreference.com/w/cpp/container/map), which take an extra template parameter that supplies the ordering. This defaults to std::less<Key> in the case of map. If you want your own ordering, you use a different comparator type when creating the map and that gets used instead. A common way to provide your own comparator is to implement a small struct that has a bool operator()(const Key& lhs, const Key& rhs) const.