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.

Solution 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.)

Solution 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.

Solution 3

IBM makes a distinction between sorted and ordered sets:

Sets can be either sorted or ordered:

• An ordered set is a set whose elements are arranged in the order in which they were added to the set. Note that this is how sets are created by default. For example:

  {int} S1 = {3,2,5}; 
  

  and

  ordered {int} S1 = {3,2,5};
  

  are equivalent.

• A sorted set is a set in which elements are arranged in their natural, ascending (or descending) order. For strings, the natural order is the lexicographic order. The natural order also depends on the system locale. For example:

  sorted {int} sortedS = {3,2,5};
  

  and

  ordered {int} orderedS = {2,3,5};
  

  are equivalent, and iterating over sortedS or orderedS will have the same behavior. To specify the descending order, you add the keyword reversed.

Also, the National Information Assurance Partnership proposed an interpretation of the terms to the National Institute of Standards and Technology in 2002:

ISSUE:

What is the distinction between the terms "sorting" and "ordering"? Sometimes the words are used interchangeably.

STATEMENT

Although the terms "sorting" and "ordering" are sometimes used interchangeably in IT system discussions, they have somewhat different meanings. When one sorts, one separates items into different kinds or classes; when one orders, one arranges the items in a particular order.

Solution 4

As words, they are almost synonyms in the context of computer code. For example:

• SQL has an order by clause, so your data rows are ordered.
• Java has a SortedSet and SortedMap interface, a Collections.sort() method for the List interface, and an Arrays.sort() method for arrays.

If I was going specify a difference, then I would say that an array or java.util.List is ordered but not sorted.

When you put objects into an array or List, they retain the order in which they were put in there, and you can access them by index, but they are not sorted, because the ordering is arbitrary.

With a java.util.SortedSet, you can put objects in, in any order you like, because it will sort them, either by natural ordering or by the formula in a java.util.Comparator. However, you cannot access the elements by index. This would make them sorted but not ordered.

Solution 5

An ordered collection implies the concept of a non-volatile, visible and reproducible address or position of its elements relative to each other. Sorting, then, is the actual placement of the elements by some arbitrary criteria.

View more solutions

Comments

[user2485710]

I still don't really get this 100%, I was thinking about saying that ordering is about expressing a predicate and sorting is just an action, but sorting implies a predicate too.

[Stuart Golodetz]

@user2485710: Sorting can take a predicate expressing the desired ordering as a parameter.

[user2485710]

can or must ? It means that is optional ? If it's optional what is the required part ?

[Stuart Golodetz]

I said "can" because often you'll be able to choose between sorting using the default ordering (generally std::less<T> in a C++ context) or supplying your own.

[Rob Kennedy]

Yes, sorting implies a predicate. The predicate defines the ordering. If you don't have an ordering, then you can't sort. Often, the predicate is implied; when you're sorting integers, the ordering is almost always numeric according to the value of the items. Since it's implied, we sometimes forget it's there and that it can be different. (Maybe we wish to order them alphabetically by how they're spelled out in English, for example.)

[user2485710]

yes, but this is a step further, it's about implementation details, what about a generic definition of this ?

[Izkata]

I would +1, except that very last statement is rather strange - "sorting" usually means changing the order according to some rule, not separating the items into different groups. That would be classification/categorization.

[Izkata]

@user2485710 Seems straightforward to me: "The numbers 1, 2, 3, 4, 5 have been sorted in ascending order". "Ordering" describes something like an adjective, while "sorting" is involves putting them in that order (a verb).

[Nenad Bulatović]

@Izkata I guess you can explain that to the National Information Assurance Partnership as it's their statement for NIST :)

[Nenad Bulatović]

"In developing this interpretation, the Oxford English Dictionary was consulted. Among the applicable definitions found were the following: SORT: To arrange (things, etc.) according to a kind or quality, or after some settled order or system; to separate and put into different sorts or classes. ORDER: The action of putting or keeping in order. in order: In proper sequence or succession, according to rank, importance, seniority, size, position, date, affinity, etc."

[Mooing Duck]

I've only heard "ordered collections" used in opposition to "unordered collections", for map/set/multimap/multiset. vector/list/array/deque are "sequence collections". Not saying you're wrong, merely that I've never heard that definition.

[cHao]

@NenadBulatovic: Never mind that no programmer (or mortal, for that matter) i know has ever used the word "order" as a verb that way. Must be a Brit thing.

[cHao]

@MooingDuck: "Sequence collections" are basically a subset of "ordered collections". They are almost the same thing, but the equivalency falls apart once you bring up things like PHP arrays (which are still sequences of a sort, in that the key/value pairs can be rearranged and have a consistent order...but which do not at all resemble what C++ would call a "sequence collection").

[Nenad Bulatović]

@cHao Could be, but NIAP and NIST are North American. IBM too. :-)

[cHao]

The "access by index" rule kinda falls apart with collections that aren't strictly lists. The Queue and Stack ADTs are ordered, for example -- but ideally only provide access to the first-inserted and last-inserted element, respectively. The index in those cases is an implementation detail that you should never even see, let alone need access to.

[Stewart]

I'd agree with that. I was mainly trying to illustrate the point that the ordering is (a) arbitrary and (b) preserved. In a SortedSet the ordering is not arbitrary, and in a normal Set the ordering is not preserved.