Sorting
Sorting refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items.
- ordering: arranging items in a sequence ordered by some criterion;
- 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
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 have been developed to perform it.
The most common uses of sorted sequences are:
- making lookup or search efficient;
- making merging of sequences efficient;
- enabling 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.
For sorting, either a weak order, "should not come after", can be specified, or a
Sorting
For example, the items are books, the sort key is the title, subject or author, and the order is alphabetical.
A new
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
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
- 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
Various sorting tasks are essential in industrial processes, such as
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] Sensor-based sorting is used in mineral processing.[1]
See also
- WP:ORDER
- Collation
- Data processing
- IBM mainframe sort/merge
- Unicode collation algorithm
- Knolling
- 5S (methodology)
References
- ISBN 978-0-87335-316-8.
External links
- Demonstration of Sorting Algorithms (includes bubble and quicksort)
- Animated video explaining bubble sort and quick sort and compares their performance.