| by Arround The Web | No comments

Counting Sort Complexity

What Is Counting Sort?

Counting sort is best illustrated with the sorting of integers. In C/C++ and Java, the characters are integers and can be sorted in the way the integers are sorted. Consider the following unsorted list of integers:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14

This list is sorted in ascending order. It can be given (received by the sort program) as an array. It consists of positive numbers greater than or equal to 0.

Notice here that the highest integer is 20. So, 20 + 1 = 21, new array locations have to be provided. The extra 1 is for the possibility that one of the integers to be sorted is 0. Remember that the sort program does not know the numbers to be sorted in advance. So, the possibility of having 0 should be made.

For each index of the new array that corresponds to a value in the given list, the number of occurrence of the value in the given list is assigned as the value for that new array cell. That is, the new array consists of counters. The previous unsorted list is represented as follows:

0 0 0 0 0 0 0 0 1 0 1 0 3 0 1 0 1 0 2 0 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

This table represents one array which is the new array of counters. At this stage, there are two arrays: the given array of the unsorted list and the array of counters called the count array.

In the table, the second row has the indexes. The first row has the counts. Each count is the number of occurrence of the corresponding index found as the value in the unsorted list.

For the indexes 0 to 7 (inclusive), the count is 0. This is because none of these indexes is a value in the given unsorted list. The index 8 occurs once in the list, so its count is 1. The index 9 occurs zero times in the list, so its count is 0. The index 10 occurs once in the list, so its count is 1. The index 12 occurs three times in the list, so its count is 3. The index 13 occurs zero times in the list, so its count is 0. This continues until the index 20 with a count of 1 while the index 18 has a count of 2.

The sorted list is as follows:

8, 10, 12, 12, 12, 14, 16, 18, 18, 20

This can be obtained from the count (new) array as follows:

Moving from left to right, if the value of an index is 0, that value is not in the given unsorted list (array). If the value is 1, type the index once. If the value is 2, type the index twice. If the value is 3, type the index three times. If the value is 4, type the index 4 times, and so on. All these can be done back on the given unsorted array (list).

Counting Sort Algorithm

  • Provide an array whose length is the maximum number in the unsorted list, plus 1 (to account for a possible 0 in the list). The index of this array is a possible value in the unsorted list.
  • Read the count array from left to right then type the index whose value is not 0 and the number of times for the index’s cell value.

Operations

The algorithm has two steps. For the previous given list, the first step has 10 main operations because the number of elements in the unsorted list is 10. The second step has 21 main operations because the maximum value in the unsorted list is 20 (the extra 1 being for a possible 0 value). So, the number of the main operations is considered as follows:

O(10 + 20)

Where 10 is the number of elements in the unsorted list and 20 is the maximum value in the unsorted list. The added 1 to 20 is ignored at this point, but bear in mind that it has to be coded.

Time Complexity for Counting Sort

Time complexity is the approximate number of the main operations for some code. Time complexity indicates the speed of the code. The time complexity for counting sort is given as follows:

O(n + m)

Where n is the number of elements (length or size) of the given unsorted array, and m is the maximum value in the given unsorted array. The added 1 to m is ignored at this point. The big-O with its parentheses and content is referred to as the big-O notation.

Note that in order to obtain the maximum value in the array, some operations have to occur in the code. However, these operations are ignored when quoting the time complexity.

The count array has to have all its elements initially made as zero. All these operations are also ignored when quoting the time complexity for the counting sort.

Memory Space

Notice that in the previous count array, all the counts of 0 are redundant. Though their spaces are redundant in memory, they have to be there. The counting sort takes unnecessary memory space in general. Nothing is normally done to avoid the redundant locations. If the minimum value in the given unsorted array can be known, the beginning part of the count array can be omitted to reduce space. However, the interspersed zeros in the count array cannot be omitted.

Note: There is also space complexity, but that is not addressed in this article.

Coding in C

A Counting Sort Function in the C computer language is as follows:

void countingSort(int arr[], int n) {
        int max = 0;
        for (int i = 0; i max) {
                max = arr[i];
            }
        }

        int count[max+1];
        for (int i = 0; i< max+1; i++) {
            count[i] = 0;
        }

        //n
        for (int i = 0; i< n; i++) {
            count[arr[i]] = count[arr[i]] + 1;  //add 1 for each occurrence
        }

        //m
        int k = 0;  //index for given array
        for (int i=0; i<max+1; i++) {
            if (count[i] != 0) {
                for (int j=0; j<count[i]; j++) {
arr[k] = i;  //putting back sorted value into given array
                    k++;
                }
            }
        }
    }

The nested for-loop and input are the following:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14

There are actually 24 major operations and not 20. The extra 3 + 1 = 4 operation is ignored when quoting the time complexity for the counting sort.

A suitable C main function is as follows:

int main(int argc, char **argv)
    {
        int n = 10;
        int arr[] = {16, 20, 12, 10, 18, 8, 12, 18, 12, 14};
countingSort(arr, n);
        for (int i=0; i<n; i++)
printf("%d ", arr[i]);
printf("\n");

        return 0;
    }

The output is:

8 10 12 12 12 14 16 18 18 20

Conclusion

The time complexity for the counting sort is:

O(n + m)

Where m is usually larger than n, n is the number of elements (length) of the given unsorted list, and m is the maximum element in the given unsorted list.

Share Button

Source: linuxhint.com

Leave a Reply