Countingsort

Countingsort (of English. Count " count " ) is a stable sorting algorithm that sorts a given sequence of integers from a bounded interval linear time ( problem complexity ) as a function of the input length. The algorithm does not work compared based, but counts the numbers of the input. In contrast, the problem of complexity Order by comparison.

• 3.1 Runtime Analysis
• 3.2 Memory Requirements

Algorithm

Countingsort assumes that the values ​​of the input to be sorted in a restricted interval (or can be easily mapped to it). The algorithm counts the number of occurrences of each of these values ​​in the input. These numbers it stores in an additional array that contains elements. Using this array, the target position in the output is calculated for each element of the input.

Input: array for all and the right interval boundary.

Edition: field with content from being sorted.

Additional memory: During the sorting of the algorithm to require an auxiliary array.

Specification of the algorithm in pseudocode:

Countingsort (A, k) {    C = array (0, k)      / / Initialize the array C with zeros    for (i = 0; i <= k; i )      C [i ] = 0    / / End for      / / Count    for (i = 1; i <= A.SIZE; i )      C [key (A [i ])] = 1    / / End for    / / Now available in C [ j] as often happens, the value j in A.      / / Address calculation    for (i = 1; i <= k; i )      C [i ] = C [i -1]    / / End for      B = array (1, A.SIZE )      / / Copy to each destination address    for (i = A.SIZE, i> 0, i - )    {      B [C [key (A [i ])] ] = A [i]      Herunterzaehlen = 1 / / target position by 1 - C [key (A [i ])]    } / / End for      return B } The key function returns the sort key of the array element type. If an array element consists only of the sort key, and contains no further components, then. In the first for loop, the auxiliary array is initialized. The second for loop iterates over the input and increments for each sort key the associated array element. In the third for loop, the counter so that means the last position of the number in the output array after the end of the loop in accumulated. The last for loop iterates through the input from right to left and decremented for each sort key in the entry, which determines the position in the output array. By iteration from right to left, the relative order of several elements of the input with the same sort key in the output is not changed, ie Countingsort sorted stable.

Simplified algorithm

If the input is a simple array of numbers, then Countingsort can be displayed without an accumulation stage:

Countingsort (A, k) {    C = array (0, k)    for (i = 0; i <= k; i = i 1)      C [i ] = 0    / / End for    for (i = 1; i <= A.SIZE; i = i 1)      C [ A [i] ] = C [ A [i] ] 1    / / End for    j = 0    B = array (1, A.SIZE )    for (i = 0; i <= k; i = i 1)      for ( C [i ]> 0, C [i] = C [i ] -1)        B [ j ] = i        j = j 1      / / End for    / / End for    return B } example

Execution of Countingsort on an input field with elements with auxiliary field and sorted output in the field.

Representation with each output list, auxiliary vector whose length depends on the definition of the list. In the lowest list the elements are inserted sorted. The figure above represents the given number sequence, wherein the first loop of the algorithm has already been processed by only the vector is initialized with 0. Second loop is incremented for each digit of their site in the vector by one.

The third loop are summed in the vector so that the content indicates to which position appears a value in the sorted list. Two identical consecutive figures indicating that the last of the two numbers do not appear in the episode, so before in at this position had been a 0. In array so now stand in place of the numbers of times a value in the array A is contained, instead ending addresses (or end- indices):

• The last value '5 ' from array A must be at index 8 in the destination array B;
• The value '4 ' came in array A is unavailable and therefore has the same final address as the value '3';
• The last '3 '- [ from array A must be at index 7 in the target array B, then the destination address C '3 ] ' is decremented by 1, so that the next '3 ' from array A to the target index 6 is replaced and thus copied to B will;
• The last '2 ' from array A must be at index 4 (ie B), further '2' he must before index 4 from A;
• '1 ' Is in A not before, so it has the same " final destination " as the value '0';
• The last '0 ' in the array A has the destination address C [ '0'], that is 2 once it has been sorted in the array B (after B), C [ '0 '] needs to be counted down by 1, so that the next '0 ', that is found in Array A, for index C [ '0' ] = 1, that is copied to the field B.

Now comes the last loop. In this, the values ​​are now gradually transferred into the vector at precisely the point in the target vector that specifies the auxiliary vector for the corresponding number. Before the loop, this is always the last point at which the number will show up. After the transfer of each number, the value is decremented in addition. The next same number is therefore a point further forward inserted in the target vector. Following the 8 steps.

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

Step 8

Complexity

Runtime Analysis

As can easily be seen from the above pseudo-code, the runtime of the function of ( the size of the payment interval ) depends on (number of elements of the input ( arrays) ) and. The for loops are each run through once or twice. The time complexity of Countingsort is so.

Memory requirements

In addition to input and output, each requiring memory arrays, a temporary array to store the frequencies of the numerical values ​​will be created. This requires elements space. The space complexity of Countingsort thus lies in.