Sort algorithm
In computer science and mathematics, a sort algorithm is an algorithm that puts elements of a list into order by means of a certain ordering, often lexicographical. Efficient sorting is important to optimizing the use of other algorithms (such as search algorithms and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output.
Sort algorithms used in computer science are often classified by:
- computational complexity (worst, average and best behaviour) in terms of the size of the list (n). Typically, good behaviour is O(n log n) and bad behaviour is O(n2). Sort algorithms which only use an abstract key comparison operation always need at least O(n log n) comparisons on average; sort algorithms which exploit the structure of the key space cannot sort faster than O(n log k) where k is the size of the keyspace.
- memory usage (and use of other computer resources)
- stability: stable sorts keep the relative order of elements that have an equal key. That is, a sort algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list. (Unstable sort algorithms can usually be made artificially stable by adding an extra number to the key defining the position in the original list.)
Sorting algorithms that are not stable can be specially implemented to be stable. One way of doing this is to artificially extend the key comparison, such that comparisons between two objects with otherwise equal keys are decided using the order of the entries in the original data order as a tie-breaker.
Some sorting algorithms follow, in typical runtime order, grouped by stability:
Stable
Unstable
Questionable sort algorithms not intended for production use:
- Bogosort - O(n × n!) expected time, unbounded worst case.
Summaries of the popular sorting algorithms
Bubble sort
The Bubble sort is the most straightforward and simplistic method of sorting data. The algorithm starts at the begining of the data set. It compares the first two elements, and if the first is greater than the second, it swaps them. The algorithm does this for each pair of adjacent elements until there are no more pairs to compare. This algorithm, however, is vastly inefficient, and is rarely used beyond the educational scope.
Insertion sort
The Insertion sort is similar to the Bubble sort, but is much more efficient as it compares an element to the previous elements (An element is compared to all the prior elements until a lesser element is found. In other words, if an element contains a value lesser than all the previous elements, it compares the element to all the previous elements before going on to the next comparison). Although this algorithm is more efficient than the Bubble sort, it is still inefficient compared to most other algorithms as it, like the bubble sort, moves elements just one position at a time.
Shell sort
The Shell sort was invented by Donald Shell in 1959. It improves upon the Bubble and Insertion sorts by arranging the data sequence in a two-dimensional array (in reality, the array is an appropriately indexed one dimensional array) and sorting the columns of the array using the Insertion sort method. Although this method is inefficient for large data sets, it is one of the fastest algorithms for sorting small numbers of elements (sets with less than 10 or so elements). Another advantage of this algorithm is that it requires reletively small amounts of memory.
See work-in-place article for the list of sort algorithms that can be written as work-in-place.
Graphical Representations
An old version of QBASIC has a file "sortdemo.bas" in the examples folder that provides a graphical representation of several of the various sort procedures described here, as well as performance ratings of each.
Also, a program by Robb Cutler called The Sorter for classic Mac OS performs a similar function. It illustrates Quick Sort, Merge Sort, Heap Sort, Shell Sort, Insertion Sort, Bubble Sort, Shaker Sort, Bin Sort, and Selection Sort.
Compare with:
External links and References
Referenced By
Algorithm | AlgorithmS | Algorithmics | List of algorithms | List of mathematical topics (S-U)
|
