Skip to main content

Counting Sort


Counting sort is a sorting algorithm that operates by counting the frequency of each element in the input array, and then using these frequencies to compute the final sorted output.

The algorithm works by first creating an array of counters, with each counter corresponding to a distinct element in the input array. The counters are initialized to zero, and then the input array is scanned once to count the number of occurrences of each element. This count information is stored in the corresponding counter in the counter array.

Once the count information is obtained, the algorithm uses it to determine the final position of each element in the sorted output array. This is done by iterating over the counter array, and for each counter value, writing the corresponding element to the sorted output array the appropriate number of times.

The time complexity of counting sort is O(n+k), where n is the length of the input array and k is the range of the elements. The space complexity is also O(n+k), since the algorithm requires a counter array of size k.

Counting sort is an efficient sorting algorithm when the range of elements is small compared to the length of the input array. In such cases, counting sort can outperform comparison-based sorting algorithms such as quicksort and mergesort, which have a worst-case time complexity of O(n log n). However, counting sort has limitations in practice, since it requires that the range of elements be known in advance, and it can also use a lot of memory for large ranges of elements.

Despite its limitations, counting sort is a useful algorithm for sorting integers with a small range of values, such as in applications involving histograms, character counts, and scoreboards. It is also used as a subroutine in other algorithms, such as radix sort and bucket sort, which extend its applicability to more general sorting problems.

ALGORITHM:

The algorithm for counting sort can be summarized in the following steps:
  1. Find the maximum value in the input array, and use this value to determine the size of the counter array.
  2. Initialize the counter array to all zeros.
  3. Iterate over the input array, and use the values as indices into the counter array. Increment the counter at each index for each occurrence of the corresponding value in the input array.
  4. Modify the counter array so that each element contains the sum of the previous elements. This step is what gives counting sort its name, since it is effectively a "counting" and "summing" process.
  5. Create a new output array of the same size as the input array.
  6. Iterate over the input array in reverse order, using the values as indices into the counter array to determine the correct position in the output array for each element.
  7. Decrement the counter at each index after placing the corresponding element in the output array.
  8. The output array now contains the sorted elements.

PSEUDO CODE:

Here is the pseudocode for counting sort algorithm:


The countingSort function takes an input array array and the maximum value of elements max_val. It first creates a counter array counter of size max_val + 1, with all elements initialized to 0. Then, it loops over the array and increments the corresponding counter in the counter array for each occurrence of a value in the array.

Next, it modifies the counter array to make it contain the cumulative sum of the previous elements in the array. This step is necessary to compute the correct position of each element in the output array.

Then, the function creates a new output array of the same size as the input array. It loops over the input array, and for each element, it uses the counter array to determine the correct position of the element in the output array. It then decrements the corresponding counter value.

Finally, the function returns the sorted output array.

PYTHON CODE:

Here is the python code for counting sort algorithm:


This implementation takes an input array arr and returns the sorted array using counting sort algorithm.

In Step 1, it finds the maximum value in the input array arr. 

In Step 2, it creates a counter array counter of size max_val + 1, with all elements initialized to 0. 

In Step 3, it loops over the arr and increments the corresponding counter in the counter array for each occurrence of a value in the arr.

In Step 4, it modifies the counter array to make it contain the cumulative sum of the previous elements in the array. This step is necessary to compute the correct position of each element in the output array.

In Step 5, it creates a new output array of the same size as the input array. 

In Step 6, it loops over the input array, and for each element, it uses the counter array to determine the correct position of the element in the output array. It then decrements the corresponding counter value.

Finally, it returns the sorted output array in Step 7.

JAVA CODE:

Here is the Java code for counting sort algorithm:



This implementation takes an input array arr and returns the sorted array using counting sort algorithm.

In Step 1, it finds the maximum value in the input array arr. 

In Step 2, it creates a counter array counter of size maxVal + 1, with all elements initialized to 0. 

In Step 3, it loops over the arr and increments the corresponding counter in the counter array for each occurrence of a value in the arr.

In Step 4, it modifies the counter array to make it contain the cumulative sum of the previous elements in the array. This step is necessary to compute the correct position of each element in the output array.

In Step 5, it creates a new output array of the same size as the input array. 

In Step 6, it loops over the input array, and for each element, it uses the counter array to determine the correct position of the element in the output array. It then decrements the corresponding counter value.

Finally, it returns the sorted output array in Step 7.

C CODE:

Here is the C code for counting sort algorithm:


This implementation takes an input array arr and its length n, and sorts the array in place using the counting sort algorithm.

In the counting_sort function, it first finds the maximum value in the input array arr. It then creates a counter array counter of size max_val + 1, with all elements initialized to 0. It loops over the arr and increments the corresponding counter in the counter array for each occurrence of a value in the arr.

It then modifies the counter array to make it contain the cumulative sum of the previous elements in the array. This step is necessary to compute the correct position of each element in the output array.

It creates a new output array of the same size as the input array. It loops over the input array in reverse order, and for each element, it uses the counter array to determine the correct position of the element in the output array. It then decrements the corresponding counter value.

Finally, it copies the sorted output array back to the input array arr, and frees the memory used by the counter and output arrays.

In the main function, it creates an example input array, calls the counting_sort function to sort it, and prints the sorted array.

C++ CODE:

Here is the C++ code for counting sort algorithm:


This implementation takes an input vector arr and sorts the vector in place using the counting sort algorithm.

In the countingSort function, it first finds the maximum value in the input vector arr. It then creates a counter vector counter of size max_val + 1, with all elements initialized to 0. It loops over the arr and increments the corresponding counter in the counter vector for each occurrence of a value in the arr.

It then modifies the counter vector to make it contain the cumulative sum of the previous elements in the vector. This step is necessary to compute the correct position of each element in the output vector.

It creates a new output vector of the same size as the input vector. It loops over the input vector in reverse order, and for each element, it uses the counter vector to determine the correct position of the element in the output vector. It then decrements the corresponding counter value.

Finally, it assigns the sorted output vector back to the input vector arr.

In the main function, it creates an example input vector, calls the countingSort function to sort it, and prints the sorted vector.

JAVASCRIPT CODE:

Here is the Javascript code for counting sort algorithm:


This implementation takes an input array arr and sorts the array in place using the counting sort algorithm.

In the countingSort function, it first finds the maximum value in the input array arr. It then creates a count array countArr of size maxVal + 1, with all elements initialized to 0. It loops over the arr and increments the corresponding count in the countArr array for each occurrence of a value in the arr.

It then modifies the countArr array to make it contain the cumulative sum of the previous elements in the array. This step is necessary to compute the correct position of each element in the output array.

It creates a new output array of the same size as the input array. It loops over the input array in reverse order, and for each element, it uses the count array to determine the correct position of the element in the output array. It then decrements the corresponding count value.

Finally, it assigns the sorted output array back to the input array arr.

In the example usage, it creates an example input array, calls the countingSort function to sort it, and prints the sorted array to the console.

Comments

Post a Comment

Popular posts from this blog

Bubble Sort

   Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. It is named after the way bubbles rise to the top of a liquid, as it sorts the array by repeatedly moving the largest or smallest elements to the top of the array. The algorithm works by iterating through the array, comparing each adjacent pair of elements and swapping them if they are in the wrong order. This process is repeated until the array is fully sorted. Let's say we have an array of integers [5, 3, 8, 4, 2]. The first pass of the algorithm would compare 5 and 3, swap them to get [3, 5, 8, 4, 2]. It would then compare 5 and 8 and not swap them, as they are in the correct order. It would then compare 8 and 4, swap them to get [3, 5, 4, 8, 2]. It would then compare 8 and 2, swap them to get [3, 5, 4, 2, 8]. The first pass is now complete, and the largest element, 8, is at the end of the array. The second pass would start with comparing 3 and 5,...
Post a Comment
Read more

Shell Sort

Shell sort is a sorting algorithm developed by Donald Shell in 1959. It is an extension of the insertion sort algorithm and is classified as an in-place comparison sort. Shell sort aims to improve the performance of insertion sort by sorting elements that are far apart from each other first, thus reducing the number of comparisons needed to sort the entire array. The algorithm works by first dividing the array into smaller subarrays, each containing elements that are a certain gap apart. The gap is typically initialized to be the length of the array divided by 2, and is then halved in each iteration until it becomes 1. The subarrays are then sorted using insertion sort, which sorts elements within each subarray by comparing adjacent elements and swapping them if they are in the wrong order. The key idea behind Shell sort is that insertion sort performs poorly on arrays that are almost sorted, but works well on small arrays. By sorting the subarrays with larger gaps first, the algorithm...
Post a Comment
Read more

Comb Sort

Comb sort is a sorting algorithm that was first proposed by Włodzimierz Dobosiewicz in 1980. The algorithm is a variation of bubble sort, and it is designed to improve upon the performance of bubble sort by using a larger gap between elements during the comparison phase of the algorithm. The basic idea behind comb sort is to compare elements that are separated by a large gap, and gradually reduce the gap between elements until the gap is equal to 1. The gap between elements is known as the "comb" in comb sort, and it is initially set to be the size of the input array being sorted. The size of the comb is then reduced by a factor known as the shrink factor, which is typically set to 1.3. During each pass of the algorithm, elements that are separated by the current gap are compared and swapped if they are out of order. The gap between elements is then reduced by the shrink factor, and the process is repeated until the gap is equal to 1. Once the gap is equal to 1, the algorithm...
Post a Comment
Read more