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.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.