• Choose a category
• All
• Classic-Fiction

By Root 1602 0

of an array of counts indexed by the integer elements themselves to keep track of how many times each one occurs. For example, if the integer 3 occurs in the data four times, 4 will be stored initially at position 3 in the array of counts. Also, we must know the largest integer in the set in order to allocate enough space for the counts.

Aside from being fast, an important virtue of counting sort is that it is stable. Stable sorts leave elements that have equal values in the same order as they appear in the original set. This is an important attribute in some cases, as we will see with radix sort.

Interface for Counting Sort

Name

ctsort

Synopsis

int ctsort(int *data, int size, int k);

Return Value

0 if sorting is successful, or -1 otherwise.

Description

Uses counting sort to sort the array of integers in data. The number of integers in data is specified by size. The argument k specifies the maximum integer in data, plus 1. When ctsort returns, data contains the sorted integers.

Complexity

O (n + k), where n is the number of integers to be sorted and k is the maximum integer in the unsorted set, plus 1.

Implementation and Analysis of Counting Sort

Counting sort works fundamentally by counting how many times integer elements occur in an unsorted set to determine how the set should be ordered. In the implementation presented here, data initially contains the unsorted set of size integer elements stored in a single block of contiguous storage. Additional storage is allocated to store the sorted data temporarily. Before ctsort returns, the sorted set is copied back into data.

After allocating storage, we begin by counting the occurrences of each element in data (see Example 12.6). These are placed in an array of counts, counts, indexed by the integer elements themselves (see Figure 12.6, step 1b). Once the occurrences of each element in data have been counted, we adjust the counts to reflect the number of elements that will come before each element in the sorted set. We do this by adding the count of each element in the array to the count of the element that follows it (see Figure 12.6, step 1c). Effectively, counts then contains the offsets at which each element belongs in the sorted set, temp.

To complete the sort, we place each element in temp at its designated offset (see Figure 12.6, steps 2a- f ). The count for each element is decreased by 1 as temp is updated so that integers appearing more than once in data appear more than once in temp as well.

Figure 12.6. Sorting with counting sort

The runtime complexity of counting sort is O (n + k), where n is the number of integers in the data and k is the largest integer value in the set being sorted, plus 1. This is because counting sort consists of three loops, two that run in time proportional to n, and one that runs in time proportional to k. For space, counting sort requires two arrays of size n and an array of size k.

Example 12.6. Implementation of Counting Sort

/*****************************************************************************

* *

* ------------------------------- ctsort.c ------------------------------- *

* *

*****************************************************************************/

#include

#include

#include "sort.h"

/*****************************************************************************

* *

* -------------------------------- ctsort -------------------------------- *

* *

*****************************************************************************/

int ctsort(int *data, int size, int k) {

int *counts,

*temp;

int i,

j;

/*****************************************************************************

* *

* Allocate storage for the counts. *

* *

*****************************************************************************/

if ((counts = (int *)malloc(k * sizeof(int))) == NULL)

return -1;

/*****************************************************************************

* *

* Allocate storage for the sorted elements. *

* *

*****************************************************************************/