Sorting
Encyclopedia
Sorting is any process of arranging items in some sequence and/or in different sets, and accordingly, it has two common, yet distinct meanings:
- ordering: arranging items of the same kind, class, nature, etc. in some ordered sequence,
- categorizingCategorizationCategorization is the process in which ideas and objects are recognized, differentiated and understood. Categorization implies that objects are grouped into categories, usually for some specific purpose. Ideally, a category illuminates a relationship between the subjects and objects of knowledge...
: grouping and labeling items with similar properties together (by sorts).
Sorting information or data
For sorting we can either specify a weak order "should not come after" or a strict weak order "should come before" (specifying one defines also the other, the two are the complement of the inverse of each other, see operations on binary relations). For the sorting to be unique, these two are restricted to a total orderTotal order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
and a strict total order, respectively.
Sorting n-tuples (depending on context also called e.g. record
Object composition
In computer science, object composition is a way to combine simple objects or data types into more complex ones...
s consisting of fields) can be done based on one or more of its components. More generally objects can be sorted based on a property. Such a component or property is called a sort key.
For example, the items are books, the sort key is the title, subject or author, and the order is alphabetical.
A new sort key can be created from two or more sort keys by lexicographical order
Lexicographical order
In mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...
. The first is then called the primary sort key, the second the secondary sort key, etc.
For example, addresses could be sorted using the city as primary sort key, and the street as secondary sort key.
If the sort key values are totally ordered
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
, the sort key defines a weak order of the items: items with the same sort key are equivalent with respect to sorting. See also stable sorting. If different items have different sort key values then this defines a unique order of the items.
A standard order is often called ascending (corresponding to the fact that the standard order of numbers is ascending, i.e. A to Z, 0 to 9), the reverse order descending (Z to A, 9 to 0). For dates/times ascending means that earlier values precede later ones e.g. 1/1/2000 will sort ahead of 1/1/2001.
In computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, sorting is one of the most extensively researched subjects because of the need to speed up the operation on thousands or millions of records during a search operation; see sorting algorithm
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
.
The main purpose of sorting information is to optimise its usefulness for specific tasks. In general, there are two ways of grouping information: by category e.g. a shopping catalogue where items are compiled together under headings such as 'home', 'sport & leisure', 'women's clothes' etc. (nominal scale) and by the intensity of some property, such as price, e.g. from the cheapest to most expensive (ordinal scale). Richard Saul Wurman
Richard Saul Wurman
Richard Saul Wurman is an architect and graphic designer who is considered to be a pioneer in the practice of making information easily understandable. Wurman has written and designed over 80 books, and created the TED conferences, but remains associated only with TEDMED.-Early life and...
, in his book Information Anxiety, proposes that the most common sorting purposes are Name, by Location and by Time (these are actually special cases of category and hierarchy). Together these give the acronym LATCH (Location, Alphabetical, Time, Category, Hierarchy) and can be used to describe just about every type of ordered information.
Often information is sorted using different methods at different levels of abstraction: e.g. the UK telephone directories which are sorted by location, by category (business or residential) and then alphabetically. New media still subscribe to these basic sorting methods: e.g. a Google search returns a list of web pages in a hierarchical list based on its own scoring system for how closely they match the search criteria (from closest match downwards).
The opposite of sorting, rearranging a sequence of items in a random or meaningless order, is called shuffling.
Physical sorting processes
Various sorting tasks are essential in industrial processes. For example, during the extraction of goldGold
Gold is a chemical element with the symbol Au and an atomic number of 79. Gold is a dense, soft, shiny, malleable and ductile metal. Pure gold has a bright yellow color and luster traditionally considered attractive, which it maintains without oxidizing in air or water. Chemically, gold is a...
from ore, a device called a shaker table uses gravity, vibration
Oscillation
Oscillation is the repetitive variation, typically in time, of some measure about a central value or between two or more different states. Familiar examples include a swinging pendulum and AC power. The term vibration is sometimes used more narrowly to mean a mechanical oscillation but sometimes...
, and flow to separate gold from lighter materials in the ore (sorting by size and weight). Sorting is also a naturally occurring process that results in the concentration of ore
Ore
An ore is a type of rock that contains minerals with important elements including metals. The ores are extracted through mining; these are then refined to extract the valuable element....
or sediment
Sorting (sediment)
Sorting indicates the distribution of grain size of sediments, either in unconsolidated deposits or in sedimentary rocks. Poorly sorted indicates that the sediment sizes are mixed ; whereas well sorted indicates that the sediment sizes are similar .The degree of sorting may also indicate the energy...
. Sorting results from the application of some criterion or differential stressor to a mass to separate it into its components based on some variable quality. Materials that are different, but only slightly so, such as the isotopes of uranium, are very difficult to separate.
See also
- CollationCollationCollation is the assembly of written information into a standard order. One common type of collation is called alphabetization, though collation is not limited to ordering letters of the alphabet...
- Sorting algorithmSorting algorithmIn computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
- Unicode collation algorithmUnicode collation algorithmThe Unicode collation algorithm is an algorithm defined in Unicode Technical Report #10, which defines a customizable method to compare two strings. These comparisons can then be used to collate or sort text in any writing system and language that can be represented with Unicode.Unicode Technical...
- OrganizingOrganizingOrganizing is the act of rearranging elements following one or more rules.Anything is commonly considered organized when it looks like everything has a correct order or placement. But it's only ultimately organized if any element has no difference on time taken to find it...
External links
- Demonstration of Sorting Algorithms (includes bubble and quicksort)
- Animated video explaining bubble sort and quick sort and compares their performance.