World Library  
Flag as Inappropriate
Email this Article


Article Id: WHEBN0000144656
Reproduction Date:

Title: Sorting  
Author: World Heritage Encyclopedia
Language: English
Subject: Sorting, Data processing, Burrows–Wheeler transform, Optical sorting, Sort
Collection: Data Processing, Sorting Algorithms
Publisher: World Heritage Encyclopedia


Sorting type

Sorting is any process of arranging items systematically, and has two common, yet distinct meanings:

  1. ordering: arranging items in a sequence ordered by some criterion;
  2. categorizing: grouping items with similar properties.


  • Sorting information or data 1
  • Physical sorting processes 2
  • A few different algorithms that are popular in computer science 3
  • See also 4
  • External links 5

Sorting information or data

In computer science, arranging in an ordered sequence is called "sorting". Sorting is a common operation in many applications, and efficient algorithms to perform it have been developed.

The most common uses of sorted sequences are:

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

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 operations on binary relations). For the sorting to be unique, these two are restricted to a total order and a strict total order, respectively.

Sorting n-tuples (depending on context also called e.g. records 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. 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, 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.

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.

Physical sorting processes

A railroad classification yard, used for sorting freight cars

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 by size and weight). Sorting is also a naturally occurring process that results in the concentration of ore or sediment. 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.

Optical sorting is an automated process of sorting solid products using cameras and/or lasers and has widespread use in the food industry.

A few different algorithms that are popular in computer science

  • Bubble 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 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.

See also

  • in WorldHeritage tables. For sorting of categories, see and for sorting of article sections, see WP:ORDER

External links

  • Demonstration of Sorting Algorithms (includes bubble and quicksort)
  • Animated video explaining bubble sort and quick sort and compares their performance.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.