39

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.

2

9 Answers 9

33
  • 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.)

2
  • 1
    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. Jun 21, 2013 at 21:03
  • @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").
    – cHao
    Jun 21, 2013 at 21:07
16

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.

7
  • 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. Jun 21, 2013 at 16:30
  • 1
    @user2485710: Sorting can take a predicate expressing the desired ordering as a parameter. Jun 21, 2013 at 16:31
  • can or must ? It means that is optional ? If it's optional what is the required part ? Jun 21, 2013 at 16:32
  • 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. Jun 21, 2013 at 16:33
  • 3
    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.) Jun 21, 2013 at 16:35
14

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.

5
  • 1
    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
    Jun 21, 2013 at 18:13
  • @Izkata I guess you can explain that to the National Information Assurance Partnership as it's their statement for NIST :) Jun 21, 2013 at 18:23
  • 3
    "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." Jun 21, 2013 at 18:33
  • @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
    Jun 21, 2013 at 21:04
  • @cHao Could be, but NIAP and NIST are North American. IBM too. :-) Jun 21, 2013 at 21:42
4

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.

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.

2
  • 1
    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.
    – cHao
    Jun 22, 2013 at 20:17
  • 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.
    – Stewart
    Jun 22, 2013 at 23:28
2

I think it helps to think of this in terms or sorting algorithms. Some sorting algorithms preserve the order while others do not. For example, consider the two naive and inefficient sorting algorithms bubble sort and selection sort. Bubble sort is guaranteed to preserves the order and selection sort is not. Preserving orders means elements which are identical don't get swapped.

Preserving order is important especially when the items contain other data that's not being sorted on. For example if you were sorting on the age of people they might have the same age but different names and you might want to preserve the original order.

See the sorting algorithms at wiki they give the time complexity and their stability. Stable means the original order is preserved.
https://en.wikipedia.org/wiki/Sorting_algorithm

1

Ranking: a comparison for partial determinate arrangement of a set; collision is possible

rank1 = max({foo1.bar, foo2.bar})
rank2 = min({foo2.kite, foo2.kite})

Ordering: composition of weighted rankings that allow a set to be completely and uniquely arranged with no latent collision; insertion order is often a fallback resolution when explicit ranking alone is inadequate for a subset

order = {
   ordering1 = (foo1.bar != foo2.bar) ? rank1(foo1, foo2) : ordering2(foo1, foo2)
   ordering2 = (foo1.kite != foo2.kite) ? rank2(foo1, foo2) : fallback(foo1, foo2)
}

Sorting: the arrangement of a set by an order using a particular access and partitioning strategy

 sort1 = strand(foo, order)
 sort2 = bubble(foo, order)

Sorted: the binary state of arrangement for a set in accordance with an order (true or false)

is_sorted = {
  for (each foo)
    (is_ordered(foo(n), foo(n-1)) ? continue : return false;
  return true;
}
1

An order relation is transitive. A sorting relation is not.
You can order a sequence of integers. You can only sort a set containing bananas, apples, berries...

1

My stab at this... Ordering is user-defined. For example you might order a set of strings based upon those most accessed, most popular etc. Sorting "generally" comes from a set of existing OS methods. Examples include sorting a set of strings alphabetically based upon string locale.

The way I see it is as follows. If I order a collection I am specifying a predicate that determines where in a collection an item will exist. If I sort a collection I am doing this usually because I want a fast look-up. Sorting usually results in fast look up times for a given item from a collection. This applies to the likes of strings, integers and so on.

Looking at my answer, I think ordering and sorting are almost interchangeable. However, I would still say that ordering is user-defined, sorting is a known concept. For example, we all know that sorting a list of names results in an alphabetical sort. If I want to sort a list of names by my own algorithm, say based upon popularity, I introduce my own sorting algorithm that orders strings as I see fit. So, I would say if you introduce an algorithm that sorts but orders the sort by your own requirements then you are ordering.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.