Home Arrays Counting Sort

# Counting Sort

0 comment

Counting sort is not a comparison sort algorithm. The sorting techniques that work on comparison are:

The best time complexity you can achieve in any of these sorting techniques is O(n * \log(n)). However, is some very specific cases, you can achieve an even faster computation time of O(n). This is made possible by an assumption. We assume that the input data set is within a finite limit.

For example, if you want to sort some characters of the English alphabet. You know that there can be a maximum of 26 characters. Similarly, if you are trying to sort marks of some students, and you know that they can range only between 0-100. These are the cases where Counting Sort can come in very handy.

#### Basic Idea:

The basic idea of counting sort is to determine, for each input element X, the number of elements smaller than X. This information can be used to place the element directly into its correct position in the resultant sorted array. For example, if there are 10 elements less than X, then X would belong at position 11 in the output array.

In the below example, arr[0..n – 1] is the input array with length n. In counting sort we need two more arrays: let us assume array count[0..n – 1] as another array and out[0..n – 1] as the final sorted array.

• Determine the range of given input elements by doing a single scan. Fig: Input array with minimum as 0 and max as 5
• Count the occurrences of each of the element and store it in an auxiliary array.
• Perform a cumulative sum on the elements of this new array.
• Use this auxiliary array to place the original elements in place. Example: temp would indicate the position of 2 in the final output array. With a 0 based indexing, 2 would go at position number 8. Repeat this process for every element of the input array.

#### Implementation and Code:

Here is an implementation of the algorithm:-

.wp-block-code {
border: 0;
}

.wp-block-code > span {
display: block;
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
static void countingSort(int[] arr)
{
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int range = max - min + 1;

// Auxiliary array to store counts of each element
int[] count = new int[range];

// Auxiliary array to store the resultant sorted array
int[] output = new int[arr.length];

// Store count of each element
for (int j : arr) {
count[j - min]++;
}

// Change count[i] so that count[i] now contains actual
// position of this character in output array
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}

// Build the output array
// To make it stable we are operating in reverse order.
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}

System.arraycopy(output, 0, arr, 0, arr.length);
}
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(n + k) where k is the range of the elements.

You can also find the sample code along with test cases on GitHub.

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More