Quicksort

Quicksort (English quick, fast ' and to sort, sort ') is a fast, recursive, non- stable sorting algorithm, based on the principle of divide and rule (Latin divide et impera! , Eng. Divide and conquer ) works. It was developed around 1960 by C. Antony R. Hoare in its basic form and since improved by many researchers. The algorithm has the advantage that it has a very short inner loop (which greatly increases the execution speed ) and without additional space makes do (apart from the additional space needed for the recursion on the call stack ).

On average, the quicksort algorithm is O (n log n ) performs comparisons. In the worst case O ( n2) comparisons are performed, but in practice very rare.

• 4.1 Running time
• 4.2 space

• 5.1 Quicksort for linked lists
• 5.2 Iterative Quicksort
• 5.3 QuickSort in functional languages

Principle

First, the list to be sorted into two sub- lists ( "left" and "right " parts list) is disconnected. For this Quicksort chooses from a so-called pivot element from the list. All elements that are smaller than the pivot element, get in the left part list, and all that are larger, in the right part list. The elements that are equal to the pivot element can be distributed anywhere on the parts list. After the division of the elements of the left list is less than or equal to the elements of the right list.

So then you just have to sort themselves in order to complete the sorting each sublist. To the Quicksort algorithm is executed respectively on the left and on the right side list. Each sublist is then again divided into two sub- lists, and applied to this again in each case the quicksort algorithm, and so on. This self- views are called recursion. If a partial list of length one or zero occurs, so this is already sorted and there is the termination of the recursion.

The positions of the elements that are equal to the pivot element are dependent on the division algorithm used. You can distribute freely to the parts lists. Since the order of equivalent elements may change each other, Quicksort is generally not stable (but stable in-place variants exist).

The process must ensure that each of the partial lists shorter by at least one than the total list. Then the recursion stops guaranteed after finitely many steps. This can be achieved, for example, that the originally selected as the pivot element is set to a space between the parts list and therefore does not belong to part list.

Pseudocode

The implementation of the division is made as an in -place algorithm: the elements are not copied to additional memory, but reversed only within the list. For this, a method is used which is referred to as a share or partition. Then, the two sub-lists are the same in the correct position. Once the parts lists have been sorted in to the sorting of the total list is completed.

Function quicksort ( left, right)       if left < right then           prime: = parts ( left, right)           quicksort (left, prime -1)           quicksort ( divider 1, right)       end   end Parts Here is the implementation of the function divides the field so that the pivot element is in its final position and all the smaller items in front of it, while all larger then come:

Functional parts ( left, right)       i: = left       / / Start with j the left of the pivot element       j: = right - 1       Pivot: = data [ right]       repeat           / / Search from the left is an element which is larger than the pivot element           repeat as long as data [ i] ≤ pivot and i < right               i: = i 1           end           / / Search from the right member, which is smaller than the pivot element           repeat as long as data [ j ] ≥ pivot and j > left                j: = j - 1           end           if i < j then               exchange data [ i] with data [ j]           end       as long as i < j / / as long as i is not moved past j       / / Swap pivot element ( data [ right] ) with a new final position ( data [ i])           if data [ i] > pivot then               exchange data [ i] with data [ right]       end             / / Give the position of the pivot element back            i answer   end After choosing the pivot element, an element from the top of the list is first starting looking for (index i), which is greater than the pivot element. According to an element from the end of the list starting smaller than the pivot element sought (index j). The two elements are then reversed and thus end up in the correct one part list. Then the two searches are continued by the positions reached, to meet the lower and upper search; there is the border between the two sublists.

Examples

Parts ( left, right)

The letters " einbeispiel " should be in alphabetical order.

Initial situation after initialization of i and j, the element on the right ( l) is the pivot element:

E i n b e i s p i e l ^ ^ i j After the first search in the inner loop i has > = l and j are held on an element < = l on an element:

E i n b e i s p i e l        ^ ^        i j After swapping the elements at i and j:

E i e c e i s p l i n        ^ ^        i j After the next search and replace:

E i e b e i n l i p s                ^ ^                i j After a further search the indexes walked past each other:

E i s b e i n l i p s                ^ ^                j i After swapping i and i denotes the pivot point of separation of the sub- lists. When i is the pivot element to the left are only elements < = pivot and right only those > Pivot:

E i e c e i l i s n p                  ^                  i Complete example for alphabetical order

In this example, the Quicksortalgorithmus to sort the letters " Quicksort ". First, the right element P > is defined as the pivot element. Then the counter g for run "bigger" from left to right, and k is "small" from right to left going

Quicksort ^ ^ ^ g kP to g encounters an element which is larger than the pivot element and to k meets an element which is smaller than the pivot element.

Qricksout    ^ ^ ^    g kP In the following step the indices continue to run k and g in the same direction as before and find items that are small in k and g is greater than the pivot element.

Qricksout         ^ ^ ^         kg P Now k and g walked past each other. This event is a termination condition. Now the pivot element is swapped with the element indexed by g.

Qricksotu         ^ ^ ^         KPG Now take the following two statements: " To the left of the pivot element, all elements less than or equal to the pivot element right of the pivot element, all elements greater than or equal to the pivot element. . "

Left |: | right   Qrickso | t | u         ^ | ^ | ^         k | P | g The pivot element " shares " now the amount of data at the location of the pivot element into two halves left and right. Now the algorithm has to the left and the right part already done in the same manner as in the foregoing taken on it. This now results in the recursion. The right part (the letter u) is only a single element and thus is sorted by definition. So the left part will be treated. The right element is again the pivot element, and the counters are set appropriately.

Qrickso | t | u ^ ^ ^ g kP Q is greater than O and k is smaller than the o

Qrickso | t | u   ^ ^ ^   g k P So the Q and k are interchanged.

KricQso | t | u   ^ ^ ^   g k P Subscripts g and k continue ...

KricQso | t | u    ^ ^ ^    g k P The r and c are exchanged.

KcirQso | t | u    ^ ^ ^    g k P In the following step, the indices have passed each other again ...

KcirQso | t | u     ^ ^ ^     kg P And ... the pivot element (letter o) is replaced with the larger element (letter r).

Left: right   kci | o | Qsr | t | u     ^ | ^ | ^ | |     k | P | g | | First, the left portion being treated.

:   kci | o | Qsr | t | u ^ ^ ^ | | ^ ^ ^ | | kP g | | g kP | |      :   cki | o | Qsr | t | u   ^ ^ ^ | | ^ ^ ^ | |   GKP | | g kP | | Letter c and k are exchanged.

:   cki | o | Qsr | t | u   ^ ^ ^ | | ^ ^ ^ | |   kg P | | g kP | | Indices have passed each other, and the element of the index g is interchanged with that of the index P.

:   cik | o | Qsr | t | u   ^ ^ ^ | | ^ ^ ^ | |   KPG | | g kP | | The resulting new now left and right part is now only of a single element and is considered sorted.

:   cik | o | Qsr | t | u      | | ^ ^ ^ | |      | | Kg P | | In the former right-hand part (letters Qsr ) the indices run right past each other, and the element in g is exchanged with the pivot element.

:   cik | o | Qrs | t | u      | | ^ ^ ^ | |      | | KPG | | This means that all characters are sorted.

Term

The running time of the algorithm depends essentially on the choice of the pivot element.

In the worst case ( worst case), the pivot element is always chosen so that it is the largest or the smallest element in the list. This is the case when the pivot element, the element is selected at the end of the list and there is always already sorted the list to be sorted. The list is to be investigated then in each recursion only one less and the time complexity is described by.

In the best case (best case ), the pivot element is always chosen so that the two resulting sub-lists are large about the same. In this case the algorithm for the asymptotic period. This also applies to the time complexity average case ( the average case ). The length of the longer of the parts list in the recursive call is namely the cut and the depth of the recursion in order.

For the choice of the pivot element, various approaches have been described in the literature. The probability of the occurrence of the worst case is a different size in these.

One possible approach is to always select the first, the last or the middle element of the list. This naive approach is relatively inefficient. Another possibility is to determine the median value of these three elements and used as a pivot member. Another approach is to select as the pivot element a random element. In this randomized quicksort is the probability that the pivot element is chosen in each division step so as to give the worst-case running time, extremely low. One can assume that he practically never occurs.

There are algorithms such as heapsort whose maturity are also limited by the worst case. In practice, however, Quicksort is still used because it is assumed that in the worst case Quicksort rarely occurs and in the central case is faster than heapsort because the innermost loop of quicksort contains only a few very simple operations. However, this is still subject of research and some of the analyzes and simulations see Heapsortvarianten forward, both from an information- theoretical considerations such as implementation considerations.

Today Quicksort is for a wide range of practical applications, the preferred sorting algorithm because it is fast and, if recursion is available, is easy to implement. In many standard libraries it already exists. Meanwhile, however, is with Introsort also an alternative available, with a comparable medium-term even for the worst case, an upper bound of guaranteed.

Space

Quicksort is an in- place method. While it swaps the elements of the list to be sorted within the list, not copies them into extra storage. It requires, however, for each recursion extra space on the stack.

As in the run- time, the memory consumption on the choice of the pivot element and the type of the data depends. In the best and average case with a recursion in, is just a stack size required.

In the worst case the number of recursions is limited only by the list length n, which requires a stack size. This can result in long lists cause a stack overflow. There are various modifications of the algorithm to solve this problem or at least reduce the likelihood of its occurrence:

• Endrekursionsbeseitigung (see the following pseudo-code )
• A more balanced choice of the pivot element (eg, median of three )
• Choosing a random pivot element, whereby systematic problems are avoided, which otherwise may result from certain pre-sorting of the elements in combination with the method of choice to Pivot
• Avoid partial lists with less than two elements (results, even if the pivot element is removed from the parts list, the maximum recursion depth )

The following pseudo code replaces the recursion ( sorting of the second sub- list) by an iteration such that the shorter part and the longer list is sorted recursive iteration. The recursion is then no greater than log (n):

Function quicksort ( left, right)       as long as the right> left repeat           prime: = parts ( left, right)           if right - prime > prime - left              quicksort (left, prime - 1) / / smaller parts list recursively ..              left: = prime 1 / / .. and larger sort iteratively           otherwise              quicksort ( prime 1, right)              right: = divider - 1           end       end   end Another possibility to avoid the additional space in linear is that first order recursive the smaller of the two sub-sequences (the other is then sorted, but also recursively). Thus, the number of not yet sorted subsequences remains limited by. For each not yet sorted subsequence two index limits are stored, each requiring additional space. Total required Quicksort with this variant extra space on the logarithmic cost measure.

Variants

QuickSort for linked lists

When shown below QuickSort variant for linked lists that each of the first to be split sequence is chosen as the pivot element. A pointer Ptr2 is pushed forward until it encounters an element that is smaller than the pivot. The elements that is passed over the Ptr2 are therefore greater than or equal to the pivot. An exchange of the first of these larger elements with at Ptr2 thus ensures that the relevant elements in the correct part of section land. PTR1 marks the end of the current partial section of elements which are smaller than the pivot. If Ptr2 has arrived at the right edge of the sequence to be split, the pivot element is swapped to the correct position between the subsequences concluded.

QuickSort (left, right );   / / Left, Right here are pointers    if Left < > Right then       Ptr1: = Links       Ptr2: = Links       Ptr0: = Links       / / Initialize the (local) pointer; Ptr0 is only required as a predecessor of Ptr1       Pivot: = Links.Zahl       repeat          Ptr2: = Ptr2.Nachfolger;          if Ptr2.Zahl < pivot then             Ptr0: = Ptr1;             Ptr1: = Ptr1.Nachfolger;             exchange ( Ptr1, Ptr2 )       until Ptr2 = Right;       swap (left, Ptr1 )       if Ptr1 < > Right then Ptr1: = Ptr1.Nachfolger;       QuickSort (left, Ptr0 );       QuickSort ( Ptr1, Right)   end The disadvantage of this method lies in the fact that lead largely sorted sequence or number of similar key values ​​to a worst-case -like behavior. Therefore, we like to choose sorting algorithms, such as mergesort, have a time complexity of the well in the worst case for linked lists. Other dynamic data structures such as balanced trees (such as B- trees, AVL trees ) spread the cost of sorting the inserts so that subsequent Order is not necessary.

Iterative Quicksort

Quicksort can be implemented non- recursively using a small stack or array. Here is a simple variant of random selection of the pivot element:

Quicksort_iterativ function ( left, right)     random: = random () / / random seed     repeat / / outer loop        while left < right repeat           Pivot: = data [ random ( left, right) ] / / select a random element located between the left and right           Sort push ( right) / / right part later           middle: = left - 1           right: = right 1           repeat / / inner loop parts box              repeat mid: = mid 1 as long as data [ middle ] < pivot              repeat right: = right - 1 as long as data [ right] > pivot              if mid > = right then abort inner loop              exchange data [ middle ] with data [ right]           split end / / field, further sort the left part        end        if stack empty then abort outer loop / / still a right part left?        left: = right 1        pop ( right) / / now sort the right part     end end The statement shall push one element on the stack where it is retrieved with pop. The random choice of the pivot element ensures a high probability for an average-case. The size of the stack is necessary with sufficient certainty less than 2 · log2 ( n ). If a limited stack still overflows, it can be easily started to sort the remaining part of the front.

The efficiency of quicksort is that it swapped elements from a great distance with each other. The shorter the list to be sorted is, the less efficient Quicksort works as it approaches a complexity of. However, the Quicksort split into multiple lists list has the property that the distance between an element and its sorted position is bounded above. Such a list sorted insertion sort in linear time, is so often canceled in the implementation below a defined sub- list length of quicksort to sort with insertion sort on.

QuickSort in functional languages

In functional languages ​​such as Haskell or Erlang is QuickSort is very easy to implement due to more powerful list processing:

Quicksort :: Ord a = > [ a] -> [ a] quicksort [ ] = [] quicksort (e: es) = quicksort [x | x <- there, x < = e ] [ e] quicksort [x | x <- there, x > e] It is the concatenation operator for lists; the pattern ( E: ) isolates the first element of the list, and [ x | x <- to x < = e ] gives all the elements of the list that are less than the pivot element E.