Sorting algorithm

A sorting algorithm is an algorithm which serves a tuple (typically an array ) to sort. Requirement is that on the set of elements a strict weak ordering is defined, such as the lexicographic order of strings or numeric order of numbers.

There are several different sorting methods, which operate with varying efficiency with respect to the time complexity (number of necessary operations ) and the space complexity ( in addition to the input array of required additional space ). The complexity of an algorithm is usually shown in the Landau notation ( see below terms like ). The time complexity depends on some sorting method from the initial arrangement of the values ​​in the array that is different then (best case ) between the best-case, average case (average behavior) and worst case (worst case ~ the values ​​are " maximum unfavorable upstream "). Often, additional factors must be considered, which influence the time or space complexity, for example, slow access to externally located data, limited amount of memory or the like.

A further distinction between stable and unstable sorting algorithm. Stable sorting process are those which do not change the relative order of elements that are equivalent with respect to the order as unstable sorting methods do not guarantee this.

In addition, a distinction is made between sorting processes which operate in-place ( in situ ), that is, the additional with a body independent of the number of elements to be sorted amount of memory space to work, and those that do not ( out-of -place or ex situ called ).

And you also distinguishes between natural sorting processes which operate at presorted data faster than unsorted data, and those that do not. Algorithms in which the control flow depending on the information, and accordingly is called adaptive sorting process that does not depend on the input data, non- adaptive. Non - adaptive algorithms are therefore particularly interesting for hardware implementations.

Manual sorting (eg index cards ) and electro- mechanical sorting methods (eg for hole cards) usually correspond to a software-based sorting methods described herein, or mixed types.

Comparison -based Order

General methods are based on the pairwise comparison of elements to be sorted. Given the complexity of analysis, it is assumed that the overhead for the comparison of two elements is constant.

Nonsensical sorting methods:

Non - comparison based sort

In the sorting methods that are not based on comparisons, the time required increases linearly with the number of elements to be sorted. For large numbers of records to be sorted, these algorithms are superior to the comparison-based methods, provided they can be applied. However, they can only be used for numeric data types.

In this case, n represents the number of elements, the number of possible values ​​of k, m, the difference between the maximum and minimum value of the input D and the number of digits of the longest entry.

Conversion of unstable processes in stable methods

An unstable sorting algorithm can be converted into a stable by the sort key is extended as a " significant digit " to each element position ( before sorting ). This will give elements that were identical in accordance with the actual sort key, a unique order.

Sort by relations

If it can be no longer sorted properties, but only after the pairwise relations, we speak of a topological sorting. This is for example the case when tasks need to be done, some tasks, however, are necessarily perform in front of others, others, however, the order does not matter.

For the topological sort, there are algorithms whose running time depends on the number of relationships. Topological sorting is not possible if mutual (cyclic ) dependencies. A topological sort does not have to be unique.

If the relationships are complete, that is, for each two objects a dependency is specified, the topological sort is transferred in an ordinary order. The runtime behavior of the algorithms for n objects is then.

Indirect Order

In cases where the switching of the data is associated with high costs, you can also use indirect Order. Additional memory is needed to proportional to the number of elements (generally 4 bytes per element). Then this array is sorted indirectly. To bring the actual data into the correct order finally, an additional cost is required by.

See also: Adapted 2-phase 2-band mixing

Proof of the lower bound for comparison -based Order

It can be proved that a comparison -based sorting algorithm can not be faster than:

Be the decision tree for a sequence. Since all permutations of the outcome of the sorting algorithm might be, the decision tree must have at least leaves. Since a minimum number of steps is sought occurred in the decision tree to avoid unnecessary comparisons.

In a decision tree with leaves, the maximum and the average depth of a leaf at least. Since a lower bound is sought, can be estimated by downward. This applies.

It remains to show that in a binary tree with leaves the maximum and the average depth of a leaf is at least. Let us assume a binary tree, for which the above statement does not apply. Be and subtrees of a binary tree with leaves. Now obviously holds for the number of sheets in or into, and. The depth of each blade relative to the root of the following applies:

The minimum of this function is now and. Used in the above equation results in:

This yields a contradiction to the assumption which the above statement is proved.