Sorting: Difference between revisions

Revision as of 10:41, 7 December 2003

Latest revision as of 16:31, 19 May 2024

(221 intermediate revisions by more than 100 users not shown)

Line 1:

{{short description|Action of arranging objects into order}}

[[fr:Tri]]

{{about|data sorting||Sort (disambiguation)|and|Sorting (sediment)}}

[[Image:Metal movable type.jpg|right|300px|thumb|Manual [[typesetting]] required all of the type after use to be sorted back into the correct slots in the [[type case]].]]

'''Sorting''' refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items.

# [[Collating order|ordering]]: arranging items in a sequence ordered by some criterion;

# [[categorization|categorizing]]: grouping items with similar properties.

Ordering items is the combination of categorizing them based on equivalent order, and ordering the categories themselves.

==By type==

'''Sorting''' refers to various ways of arranging or ordering things.

==={{anchor|Sort/Merge}}Information or data===

In {{visible anchor|[[computer science]]}}, arranging in an ordered sequence is called "sorting". Sorting is a common operation in many applications, and efficient [[Sorting algorithm|algorithms]] have been developed to perform it.

The most common uses of sorted sequences are:

==Sorting information or data==

* making [[search algorithm|lookup or search]] efficient;

* making [[merge algorithm|merging of sequences]] efficient;

* enabling [[data processing|processing of data]] in a defined order.

The opposite of sorting, rearranging a sequence of items in a random or meaningless order, is called [[shuffling]].

One important kind of sorting is arranging items of information in sequence according to some pre-defined ordering, e.g. when one sorts the books in a library alphabetically by title, subject or author. The problem of how to change the order of lists according to given criteria is simply called '''sorting''' in [[computer science]]. It is one of extensively researched subjects in it; see [[sort algorithm]].

For sorting, either a weak order, "should not come after", can be specified, 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 [[Binary relation#Operations|operations on binary relations]]). For the sorting to be unique, these two are restricted to a [[total order]] and a strict total order, respectively.

The main purpose of sorting information is to optimise its usefulness for specific tasks. In general, there are two ways of sorting information: '''by category''' e.g. a shopping catalogue where items are grouped together under headings such as 'home', 'sport & leisure', 'women's clothes' etc. and '''in a hierarchy''' according to some property e.g. from cheapest to most expensive. Richard Saul Wurman, in his book '''Information Anxiety''', proposes '''Alphabetical''', by '''Location''' and by '''Time''' as being the most common sorting methods (these are actually special cases of category (___location, alphabetical) and hierarchy (time). Together these give the acronym LATCH (Location, Alphabetical, Time, Category, Hierarchy) and can be used to describe just about every type of ordered information.

Sorting [[n-tuple]]s (depending on context also called e.g. [[Object composition|record]]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'''.

==Physical sorting processes==

For example, the items are books, the sort key is the title, subject or author, and the order is alphabetical.

Various sorting tasks are essential in industrial processes. For example, during the extraction of [[gold]] from ore, a device called a [[shaker table]] uses [[gravity]], [[vibration]], and [[flow]] to separate gold from lighter materials in the ore. Sorting is also a naturally occurring process that results in the concentration of [[ore]]. 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.

A new [[collation#sort keys|sort key]] can be created from two or more sort keys by [[lexicographical order]]. 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 [[total order|totally ordered]], the sort key defines a [[strict weak ordering#Total preorders|weak order]] of the items: items with the same sort key are equivalent with respect to sorting. See also [[Sorting algorithm#Stability|stable sorting]]. If different items have different sort key values then this defines a unique order of the items.

[[File:Bundesarchiv Bild 183-22350-0001, Berlin, Postamt O 17, Päckchenverteilung.jpg|thumb|Workers sorting parcels in a postal facility]]

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 and times, ''ascending'' means that earlier values precede later ones e.g. 1/1/2000 will sort ahead of 1/1/2001.

====Common algorithms====

{{main|Sorting algorithm}}

* '''[[Bubble sort|Bubble]]/[[Shell sort]]''': Exchange two adjacent elements if they are out of order. Repeat until array is sorted.

* '''[[Insertion sort]]''': Scan successive elements for an out-of-order item, then insert the item in the proper place.

* '''[[Selection sort]]''': Find the smallest (or biggest) element in the array, and put it in the proper place. Swap it with the value in the first position. Repeat until array is sorted.

* '''[[Quick sort]]''': Partition the array into two segments. In the first segment, all elements are less than or equal to the pivot value. In the second segment, all elements are greater than or equal to the pivot value. Finally, sort the two segments recursively.

* '''[[Merge sort]]''': Divide the list of elements in two parts, sort the two parts individually and then merge it.

===Physical===

{{redirect|Shaker table|tables made by Shakers|Shaker furniture}}

[[File:Potomac Yard - aerial 1980s.jpg|thumb|A railroad [[classification yard]], used for sorting [[freight car]]s]]

Various sorting tasks are essential in industrial processes, such as [[mineral processing]]. For example, during the extraction of [[gold]] from ore, a device called a [[shaker table]] uses [[gravity]], [[oscillation|vibration]], and [[flow]] to [[separation process|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]] or [[Sorting (sediment)|sediment]]. Sorting results from the application of some criterion or differential stressorstressors 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.

[[Optical sorting]] is an automated process of sorting solid products using cameras and/or lasers and has widespread use in the food industry.{{citation needed|date=August 2019}} [[Sensor-based sorting]] is used in mineral processing.<ref name="Malhotra2009">{{cite book|author=Deepak Malhotra|title=Recent Advances in Mineral Processing Plant Design|url=https://books.google.com/books?id=q1iiQUczjuQC&q=%22sensor-based+sorting%22|year=2009|publisher=SME|isbn=978-0-87335-316-8}}</ref>

==See also==

* [[Help:Sortable tables|Help:Sorting]] in Wikipedia tables. For sorting of categories, see [[Wikipedia:Categorization#Sort keys]] and for sorting of article sections, see [[WP:ORDER]]

* [[Collation]]

* [[Data processing]]

* [[IBM mainframe utility programs#IBM SORT|IBM mainframe sort/merge]]

* [[Unicode collation algorithm]]

* [[Knolling]]

* [[5S (methodology)]]

==References==

{{Reflist}}

==External links==

{{wiktionary|sort|sorting}}

* [https://web.archive.org/web/20061008105719/http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html Demonstration of Sorting Algorithms] (includes bubble and quicksort)

* [https://www.youtube.com/watch?v=vxENKlcs2Tw Animated video] explaining bubble sort and quick sort and compares their performance.

{{commons category}}

[[Category:Sorting algorithms]]

[[Category:Data processing]]