| |
|
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.
| Table of contents |
|
2 Summaries of the popular sorting algorithms 3 Graphical Representations 4 External links and References |
Classification
Sort algorithms used in computer science are often classified by:
(4, 1) (3, 1) (3, 7) (5, 6)
In this case, two different results are possible, one which preserves the order of "equal" elements in the original, and one which doesn't:
(3, 1) (3, 7) (4, 1) (5, 6) (stable) (3, 7) (3, 1) (4, 1) (5, 6) (unstable)
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, so 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:Summaries of the popular sorting algorithms
Bubble sort
The Bubble sort is the most straightforward and simplistic method of sorting data that could actually be considered for real world use. 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, then repeats until no swaps have occurred on the last pass. 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 except in education (ie, beginning programming classes). A slightly better variant is generally called shuttle sort, and works by inverting the ordering criteria, and the pass direction on alternating passes.
See work-in-place article for the list of sort algorithms that can be written as work-in-place.
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:
Insertion sort
The Insertion sort is similar to the Bubble sort, but is more efficient as it reduces element comparisions somewhat with each pass. An element is compared to all the prior elements until a lesser element is found. In other words, if an element contains a value less 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 many other sort algorithms since it, and bubble sort, move elements only 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 moving out of order elements more than one position at a time. One implementation can be described as arranging the data sequence in a two-dimensional array (in reality, the array is an appropriately indexed one dimensional array) and then 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 relatively small amounts of memory.Merge sort
The merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (e.g. 1 and 2, 3 and 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two, then sorting the resulting lists of four, and so on.Heapsort
**** to be written ****
Radix sort
**** to be written ****
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.External links and References