Sorting algorithm
|
|
In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output.
| Contents |
Classification
Sorting 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 Ω(n2). Ideal behaviour for a sort is O(n). Sort algorithms which only use an abstract key comparison operation always need at least Ω(n log n) comparisons on average;
- memory usage (and use of other computer resources)
- stability: stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting 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.
- general method: insertion, exchange, selection, merging, etc. Exchange sorts include bubble sort and quicksort. Selection sorts include shaker sort and heapsort.
When equal elements are indistinguishable, such as with integers, stability is not an issue. However, assume that the following pairs of numbers are to be sorted by their first coordinate:
(4, 1) (3, 1) (3, 7) (5, 6)
In this case, two different results are possible, one which maintains the relative order of records with equal keys, and one which does not:
(3, 1) (3, 7) (4, 1) (5, 6) (order maintained) (3, 7) (3, 1) (4, 1) (5, 6) (order changed)
Unstable sorting algorithms may change the relative order of records with equal keys, stable sorting algorithms never do so. Unstable sorting algorithms 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. Remembering this order, however, often involves an additional space penalty.
List of sorting algorithms
In this table, n is the number of records to be sorted and k is the number of distinct keys.
Stable
- Bubble sort — O(n2)
- Cocktail sort (bidirectional bubble sort) — O(n2)
- Insertion sort — O(n2)
- Bucket sort — O(n); requires O(k) extra memory
- Counting sort — O(n+k); requires O(n+k) extra memory
- Merge sort — O(n log n); requires O(n) extra memory
- In-place merge sort — O(n2)
- Binary tree sort — O(n log n); requires O(n) extra memory
- Pigeonhole sort — O(n+k); requires O(k) extra memory
- Radix sort — O(n·k); requires O(n) extra memory
- Gnome sort — O(n2)
Unstable
- Selection sort — O(n2)
- Shell sort — O(n log n) if best current version used
- Comb sort — O(n log n)
- Heapsort — O(n log n)
- Smoothsort — O(n log n)
- Quicksort — O(n log n) expected time, O(n2) worst case; generally believed to be the fastest known sort for large, random lists
- Introsort — O(n log n)
- Patience sorting — O(n log n + k) worst case time, requires additional O(n + k) space, also finds the longest increasing subsequences
Impractical sort algorithms
- Bogosort — O(n × n!) expected time, unbounded worst case.
- Stupid sort — O(n3); recursive version requires O(n2) extra memory
- Bead Sort — O(n) or O(√n), but requires specialized hardware
- Pancake sorting — O(n), but requires specialized hardware
Summaries of the popular sorting algorithms
Bubble sort
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 beginning 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 (i.e., beginning programming classes). A slightly better variant is generally called cocktail sort, and works by inverting the ordering criteria and the pass direction on alternating passes.
Insertion sort
Insertion sort is similar to bubble sort, but is more efficient as it reduces element comparisons 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. However, insertion sort is a good choice for small lists (about 30 elements or fewer), and for nearly-sorted lists. These observations can be combined to create a variant of insertion sort which works efficiently for larger lists. This variant is called shell sort (see below).
Shell sort
Shell sort was invented by Donald Shell in 1959. It improves upon bubble sort and insertion sort 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 1000 or so elements). Another advantage of this algorithm is that it requires relatively small amounts of memory.
See in-place algorithm for a list of sorting algorithms that can be written to work in-place.
Merge sort
Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e. 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list.
Heapsort
Heapsort is a member of the family of selection sorts. This family of algorithms works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list. Straight selection sort runs in O(n2) time, but Heapsort accomplishes its task efficiently by using a data structure called a heap, which is a binary tree where each parent is larger than either of its children. Once the data list has been made into a heap, the root node is guaranteed to be the largest element. It is removed and placed at the end of the list, then the remaining list is "heapified" again.
Radix sort
Some radix sort algorithms are counterintuitive, but they can be surprisingly efficient. If we take the list to be sorted as a list of binary strings, we can sort them on the least significant bit, preserving their relative order. This "bitwise" sort must be stable, otherwise the algorithm will not work. Then we sort them on the next bit, and so on from right to left, and the list will end up sorted. This is most efficient on a binary computer (which nearly all computers are). If we had a ternary computer, we would regard the list as a list of base 3 strings and proceed in the same way. Most often, the bucket sort algorithm is used to accomplish the bitwise sorting.
Radix sort can also be accomplished from left to right, but this makes the algorithm recursive. On a binary (radix 2) computer, we would have to sort on the leftmost bit, and then sort the sublist with 0 as the leftmost bit, and then sort the sublist with 1 as the leftmost bit, and so on.
Memory Usage Patterns and Index Sorting
When the size of the array to be sorted approaches or exceeds the available primary memory, so that (much slower) disk or swap space must be employed, the memory usage pattern of a sorting algorithm becomes important, and an algorithm that might have been fairly efficient when the array fit easily in RAM may become impractical. In this scenerio, the total number of comparisons becomes (relatively) less important, and the number of times sections of memory must be copied or swapped to and from the disk can dominate the performance characteristics of an algorithm. Thus, the number of passes and the localization of comparisons can be more important than the raw number of comparisons, since comparisons of nearby elements to one another happen at system BUS speed (or, with cacheing, even at CPU speed), which, compared to disk speed, is virtually instantaneous.
For example, the popular recursive quicksort algorithm provides quite reasonable performance with adequate RAM, but due to the recursive way that it copies portions of the array it becomes much less practical when the array does not fit in RAM, because it may cause a number of slow copy or move operations to and from disk. In that scenerio, another algorithm may be preferable even if it requires more total comparisons.
One way to work around this problem, which works well when complex records (such as in a relational database) are being sorted by a relatively small key field, is to create an index into the array and then sort the index, rather than the entire array. (A sorted version of the entire array can then be produced with one pass, reading from the index, but often even that is unnecessary, as having the sorted index is adequate.) Because the index is much smaller than the entire array, it may fit easily in memory where the entire array would not, effectively eliminating the disk-swapping problem.
Another technique for overcoming the memory-size problem is to combine two algorithms in a way that takes advantages of the strength of each to improve overall performance. For instance, the array might be subdivided into chunks of a size that will fit easily in RAM (say, a few thousand elements), the chunks sorted using an efficient algorithm (such as quicksort or heapsort), and the results merged as per mergesort. This is more efficient than just doing mergesort in the first place, but it requires less physical RAM (to be practical) than a full quicksort on the whole array.
Techniques can also be combined. For sorting really enormous amounts of data that completely dwarf system memory, even the index may need to be sorted using an algorithm or combination of algorithms designed to perform reasonably with virtual memory, i.e., to reduce the amount of swapping required.
Graphical representations
Microsoft's "Quick" programming languages (such as QuickBASIC and QuickPascal) have a file named "sortdemo" (with extension BAS and PAS for QB and QP, respectively) 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 (http://faculty.harker.org/robbc/Pages/Software/TheSorter/TheSorter.htm) 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.
Finally, at the University of British Columbia, Jason Harrison has a page (http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html) graphically demonstrating the activity of various in-place sorts.
See also
External links and references
- D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching.
- Introduction to Algorithms, Second Edition, by Cormen, Leiserson, Rivest, and Stein. (http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JIntroduction-to-AlgorithmsFall2001/CourseHome/index.htm)
- [1] (http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm) has explanations and analyses of many of these algorithms.
- [2] (http://www.aeriesoft.ru/Projects/SortAlg/) has information on many of these algorithms.
- Ricardo Baeza-Yates' sorting algorithms on the Web (http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html)
- 'Dictionary of Algorithms, Data Structures, and Problems' (http://www.nist.gov/dads/)
- For some slides and PDFs see Manchester university's course notes (http://www.cs.man.ac.uk/~graham/cs2011.html)
- For a repository of algorithms with source code and lectures, see The Stony Brook Algorithm Repository (http://www.cs.sunysb.edu/~algorith/)
- Graphical Java illustrations of the Bubble sort, Insertion sort, Quicksort, and Selection sort (http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html)
- xSortLab (http://math.hws.edu/TMCM/java/xSortLab/) - An interactive Java demonstration of Bubble, Insertion, Quick, Select and Merge sorts, which displays the data as a bar graph with commentary on the workings of the algorithm printed below the graph.
- Sorting Algorithms Demo (http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html) - Java applets that chart the progress of several common sorting algorithms while sorting an array of data using in-place algorithms.
- [3] (http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/sortcontest/sortcontest.htm) - An applet visually demonstrating a contest between a number of different sorting algorithms
- sortchk (http://www.home.unix-ag.org/bmeurer/projects/sortchk/) - a sort algorithm test suite released under the terms of the BSD License (original)
- The Three Dimensional Bubble Sort (http://www.magma.ca/~gtaylor/3dBubbleSort.htm)- A method of sorting in three or more dimensions (of questionable merit)
de:Sortierverfahren es:Algoritmos de ordenamiento fr:Algorithme de tri he:מיון (מחשבים) lt:Rūšiavimo algoritmas nl:Sorteer-algoritme ja:ソート pl:Sortowanie fi:Lajittelualgoritmi sv:Sorteringsalgoritm zh-cn:排序算法