# A Report On Count Sort Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In computer science and mathematics, a sorting algorithm is an algorithm that puts element of a list in a certain order. Efficient sorting is important for optimizing the use of the other algorithm (such as search and merge algorithm)that requires sorted list to work correctly. It is useful for producing human readable output. More formally, the output must satisfy two conditions:

1. The output is non decreasing order.

2. The output is permutation, or reordering of the input.

Since the dawn of computing, the sorting problem has attracted a great deal of research, perhaps due to the complexity of solving it efficiently despite its simple, familiar statement and count sort is one of the major sorting technique.

The basic idea of counting sort is to determine, for each input element x, the number of element less than x. this information can be used to place element x directly into its position in the output array. For example, if there are 17 elements less then x, then x belongs in output position 18. This scheme must be modified slightly to handle the situation in which several elements have the same value, since we don't want to put them all in the same position.

## Introduction

Count sort is the linear sorting algorithm. Linear sorting is that sorting which is not based on comparisons like most other sorting methods are, and its time complexity is thus not bounded by O(nlogn) as all comparison sorts are. It does not use any comparison operators like >, <, <=,>= and ==to determine the sorting order of the elements. This method of sorting is used when all elements to be sorted are in a known, finite and in a small range. The sorting is achieved by acute logic build and the overall time taken by algorithm is linear.

Count sort takes the advantage of knowing the maximum value within the elements of the array to be sorted. If the maximum value within the array is not known, initially it is necessary to find out the maximum value in the first pass of the data. It uses this maximum value to create an auxiliary array (referenced by the values within the array to be sorted) that will serve to count the number of values of a certain number and, after this the positions of the values on a third array is determined, which is the final sorted array of the second array.

Count sort is a efficient and a linear sorting algorithm which sort the element in O(n) time which is the fundamental building block of many applications .It uses the range to create an arrayÂ CÂ of this length. Each indexÂ iÂ in arrayÂ CÂ is then used to count how many elements inÂ AÂ have the valueÂ i; then counts stored inÂ CÂ can then be used to put the elements in A into their right position in the resulting sorted array.

Count Sort works by counting the occurrences of each data value. It assumes that there are n data items in the range of 1..k, where k is an integer. The algorithm can then determine, for each input element, the amount of elements less than it.

For example if there are 9 elements less than element x, then x belongs in the 10th data position.

The counting sort is a stable sort. It preserves the input order among equal elements.

A: 4 1 3 4 3

B: 1 3 3 4 4

When we have a list of students sorted by last name, then a counting sort is used to sort by grade A B C D F, the final list will be sorted primarily by grade, but all the students who got the same grade will still be sorted by last name.

## Characteristics of count sort

Count sort is a stable sorting which has a running time of O(n+k), where n and k are the lengths of the arrays A (the input array) and C (the counting array), respectively. In order for this algorithm to be efficient, k must not be greater than n.

Numbering is done in the C(counting array) from the minimum value in A(input array) to the maximum value of A. If the minimum and maximum values of A are not known, an initial pass of the data will be necessary to find these (this pass will take time O(n).

Count sort algorithm is only suitable for sorting the numbers whose range is small, for example between 0 and 100, but it is unsuitable for sorting a list of names alphabetically. However, it can be used with radix sort to sort a list of integers whose range is too large.

Count sort is not the comparison sort.

## Algorithm :

A summary of the algorithm is as follows.

Finding the highest and the lowest elements of the array.

Counting the numbers of the elements in the array. (For E.g.int the array [4,4,4,1,1] there is three 4's and two 1's)

And then store zero 0's, two 1's, zero 2's, zero 3's, and three 4's into the output array.

## Working mechanism with example

Suppose that the values to be sorted are all between 0 and k, where k is some (small) integer. Assume the values are in the array A[1â€¦n].

1. Use an array C[0...k] to count how many times each key occurs in A. This requires O(n) time.

2

5

3

0

2

3

0

3 A:

1 2 3 4 5 6 7 8

2

0

2

3

0

1 C:

0 1 2 3 4 5

2. Calculate cumulative totals in C. The time is O(k).

2

2

4

7

7

8

C:

0 1 2 3 4 5

These numbers tell us, for example, that the three occurrences of 3 should be in places 5,6,7 of the final array.

3. Copy data into the target array B. The time is O(n).

for i = n downto 1

B[C[A[i]]] â†âˆ’ A[i]

C[A[i]] â†âˆ’ C[A[i]] - 1

1 2 3 4 5 6 7 8

2

5

3

0

2

3

0

3

A:

3

B:

2

2

4

6

7

8

C:

0 1 2 3 4 5

0

3

3

B:

1

2

4

5

7

8

C:

0 1 2 3 4 5

0

2

3

3

B:

1

2

3

5

7

8

C:

0 1 2 3 4 5

0

0

2

3

3

B:

0

2

3

5

7

8

C:

0 1 2 3 4 5

0

0

2

2

3

3

B:

0

2

2

4

7

7

C:

0 1 2 3 4 5

Assuming k = O(n), the total time is O(n) which is better than other comparison sort.

## Pseudocode

In the pseudocode of Counting sort, we are given input arrayÂ A[1 . . .Â n]Â of lengthÂ n to be sorted. Each value in A is an integer of the range 1 through k. We required two more arrays, the arrayÂ B[1 . . .Â n] which holds the sorted output and the arrayÂ c[1 . .Â . k] provides temporary working storage. The pseudocode is as follows,

Count Sort (A, B, k)

1. for i = 1 to k do // Initialize counters.

C[i] = 0

// At the end of the following for loop, C[i] stores //the number of keys equal to i.

2. for j = 1 to n do

C[A[j]] = C[A[j]]+1 // At the end of the following for loop, C[i] stores

// the number of keys less than or equal to i.

3. for i = 2 to k do

C[i] = C[i] + C[i-1] // The following loop uses "down to" to ensure a //stable sort.

4. for j = n down to 1 do

// Place A[j] in its correct position.

5. B[C[A[j]]] = A[j]

// If there is another key equal to A[j], it will

// go before the current A[j]

6. C[A[j]] = C[A[j]] - 1

The procedure is as follow:

Count the occurrence of an element i in A, and put in C, which means C[i] contains how many occurrence of element i in array A.

Accumulate the counts, till C[i] contains the number of elements less or equal to i.

Fill into output array B from backwards by putting each element i to countthÂ position in B, and each time decreasing counts of element i in C.

## Implementation of the count sort algorithm in C

#include<stdio.h>

#include<conio.h>

#include <stdlib.h>

void counting_sort(int a[], unsigned int length, int num_values) {

unsigned int i;

unsigned int j, output_pos;

int* counts = malloc(sizeof(int) * num_values);

if (counts == NULL) {

printf("Out of memory\n");

exit(-1);

## }

for(i=0; i<length; i++) {

counts[a[i]]++;

## }

output_pos = 0;

for (i=0; i<num_values; i++) {

for (j=0; j<counts[i]; j++) {

a[output_pos] = i;

output_pos++;

## }

## }

Free(counts);

## }

## Data Structures involved

Data structures is the organization of data for effective fetching and manipulation.It help us to unstand the relation of data and items.Here in the count sort data structures involved is array.Array is the set of elements.

At first, the counting sort variable is declared.

Then, count loop begins.

The use of a[i] as an array index. This makes counting sort not a comparison sort.

Then, we iterate though the counts array, outputting the counted number of elements for each value.

Although, next there is doubly-nested loop, the way in which we set the counters guarantees that the inner loop is executed only a linear(O(n)) number of times. Putting together the two phases.

The sort is now complete.

## Analysis of the sorting algorithms (best case, worst case):

counting-sort(A,B,k)

1. For iâ† 1 to k do

2. c[i] â†0

3. for j â† 1to n do

4. for c[A[J]] â†Â c[A[j]] + 1

5. // c[i] now contains the number of elements equal to i

6. for I â†Â 2 to k do

7. c[i] â†Â c[i] + c[i-1]

8. // c[i] now contains the number of elements â‰¤ i

9. for j â†Â n downto 1

10. B[c[A[i]]] â†Â A[j]

11. c[A[i]] â†Â c[A[j]]-1

In the above pseudocode ,

The loop of lines 1-2Â Â takesÂ O(k)Â time.

The loop of lines 3-4Â Â takesÂ O(n)Â time.

The loop of lines 6-7Â Â takesÂ O(k)Â time.

The loop of lines 9-11 takesÂ O(n)Â time.

## Time Complexity:

Counting sort has a running time of O(nÂ +Â k), whereÂ nÂ is the number of elements to be sorted andÂ kÂ is the range of those numbers. IfÂ kÂ =Â O(n), this algorithm has O(n) performance. Here all the best case, worst case and average case is O(nÂ +Â k).

## Space Complexity:

Counting sort does not sort in place, since it creates two other arrays, counting array C and output array. The space complexity is O(nÂ +Â k), where n and k are the length of the array A and C, respectively. No swap operations is performed during the process.

## Stability:

The Counting sort is a stable sortÂ i.e., multiple keys with the same value are placed in the sorted array in the same order that they appear in the input array.

Suppose that the for-loop in line 9 of the Counting sort is rewritten:

9Â Â Â for jÂ â†Â 1 to n

then the stability no longer holds.

## Conclusion:

Counting sort is aÂ stable sortÂ and has a running time ofÂ O(n+k), whereÂ nÂ andÂ kÂ are the lengths of the arraysÂ AÂ (the input array) andÂ CÂ (the counting array), respectively. In order for this algorithm to be efficient,Â kÂ must not be much larger thanÂ n.

The indices ofÂ CÂ must run from the minimum to the maximum value inÂ AÂ to be able to indexÂ CÂ directly with the values ofÂ A. Otherwise, the values ofÂ AÂ will need to be translated (shifted), so that the minimum value ofÂ AÂ matches the smallest index ofÂ C. If the minimum and maximum values ofÂ AÂ are not known, an initial pass of the data will be necessary to find these (this pass will take time Î˜(n);

The length of the counting arrayÂ CÂ must be at least equal to the range of the numbers to be sorted (that is, the maximum value minus the minimum value plus 1). This makes counting sort impractical for large ranges in terms of time and memory needed. Counting sort may for example be the best algorithm for sorting numbers whose range is between 0 and 100, but it is probably unsuitable for sorting a list of names alphabetically. However, counting sort can be used withÂ radix sortÂ to sort a list of integers whose range is too large for counting sort to be suitable alone.

Because counting sort uses key values as indexes into an array, it is not aÂ comparisons sort, and the Î©(nÂ logÂ n) lower-bound for sorting is inapplicable.

Counting sort is commonly used within other sorting algorithms such asÂ radix sort, since radix sort processes by counting occurrence of digits of a limited number of bits, thus limiting the size of the count table.