# Sorting algorithm

### From Wikipedia, the free encyclopedia.

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 [showhide] |

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 O(*n*^{2}). 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 sorting algorithms**maintain the relative order of records with equal keys. 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.

When equal elements are indistinguishable, such as with integers, stability is not an issue. However, say we were sorting these pairs of numbers 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 records with equal keys, and one which doesn't:

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

__edit__]

## Table of sorting algorithms

In this table, *n* is the number of records to be sorted, *k* is the number of distinct keys, and *u* is the number of unique records.

__edit__]

### Stable

__Bubble sort__- O(*n*^{2})__Cocktail sort__(bidirectional bubble sort) - O(*n*^{2})__Insertion sort__- O(*n*^{2})__Bucket sort__- O(*n*); requires O(*n*) 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(*n*^{2}) __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(*nk*); requires O(*n*) extra space__Stupid sort__- O(*n*^{3}); recursive version requires O(*n*^{2}) extra memory__Gnome sort__- O(*n*^{2})

__edit__]

### Unstable

__Selection sort__- O(*n*^{2})__Shell sort__- O(*n*log*n*) if best current version used, may be even better unknown variants.__Comb sort__- O(*n*log*n*)__Heapsort__- O(*n*log*n*)__Smoothsort__- O(*n*log*n*)__Quicksort__- O(*n*log*n*) expected time, O(*n*^{2}) worst case__Several Unique Sort__- O(*n*u) expected time, O(*n*^{2}) worst case, when u=n and where u is the number of the unique records

Questionable sort algorithms not intended for production use:

__Bogosort__- O(*n*×*n*!) expected time, unbounded worst case.__Pancake sorting__- O(*n*), but not for__Von Neumann machines__.

__edit__]

## Summaries of the popular sorting algorithms

__edit__]

### 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 __shuttle sort__, and works by inverting the ordering criteria, and the pass direction on alternating passes.

__edit__]

### 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).

__edit__]

### 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 10 or so elements). Another advantage of this algorithm is that it requires relatively small amounts of memory.

See __work-in-place__ article for the list of sorting algorithms that can be written as work-in-place.

__edit__]

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

__edit__]

### 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(n*^{2}*)* 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.

__edit__]

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

__edit__]

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

__edit__]

## See also

__sorting networks__(compare)__collation__

__edit__]

## External links and references

- D. E. Knuth,
.__The Art of Computer Programming__, Volume 3: Sorting and Searching __[1]__(*http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm*) has 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 Bubblesort , Insertionsort , Quicksort , and Selestsort__(*http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html*)__sortchk__(*http://www.home.unix-ag.org/bmeurer/projects/sortchk/*) - a sort algorithm test suite released under the terms of the__BSD License__(original)

#### 'JAVA > JSE' 카테고리의 다른 글

FileFilter... 까먹기 싫어~~~ (0) | 2005.02.12 |
---|---|

[nio] Channels 클래스 (0) | 2005.01.17 |

[펌] Sorting Algorithm (0) | 2005.01.15 |

[link] 자바 검색 봇~ (0) | 2005.01.11 |

[펌] [Collection Framework ] List, Set and Map (0) | 2004.12.29 |

소스포지.. 디컴파일해두 소스 안보여주는 (0) | 2004.11.23 |

## 댓글을 달아 주세요