For each element in the list, counting sort determines the number of elements that are less than it. Note: For a sorting algorithm to be stable, the order of elements with equal keys (values) in the sorted array should be the same as that of the input array.Counting sort assumes that each of the n n n input elements in a list has a key value ranging from 0 0 0 to k k k, for some integer k k k. Few examples of comparison based sorting algorithms are quick sort, merge sort, bubble sort, selection sort, heap sort, insertion sort, whereas algorithms like radix sort, bucket sort and comparison sort fall into the category of non-comparison based sorting algorithms. A comparison-based sorting algorithm sorts numbers only by comparing pairs of numbers. It is an integer-based sorting algorithm unlike others which are usually comparison-based.It will not work if we have 5 elements to sort in the range of 0 to 10,000 Counting Sort algorithm is efficient if the range of input data (k) is not much greater than the number of elements in the input array (n).Since counting sort is suitable for sorting numbers that belong to a well-defined, finite and small range, it can be used asa subprogram in other sorting algorithms like radix sort which can be used for sorting numbers having a large range.The above implementation of Counting Sort can also be extended to sort negative input numbers.Thus the total running time for counting sort algorithm is O(n+k). The count array also uses k iterations, thus has a running time of O(k). The sorted array B also gets computed in n iterations, thus requiring O(n) running time. Time Complexity Analysisįor scanning the input array elements, the loop iterates n times, thus taking O(n) running time. Note: The algorithm can be mapped to any programming language as per the requirement. The input array is the same as that used in the example: B is the output array having the sorted elements A is the input array and will store elements entered by the user Int k=0 // for storing the maximum element of input array Program for Counting Sort Algorithmīelow we have a simple program in C++ implementing the counting sort algorithm: #include Thus, array B has the sorted list of elements. After adding 2 to B, count=4 and i=3įor i=3, t=8, count= 10, v=9. Step 3: Add elements of array A to resultant array B using the following steps: Step 2: Using the formula, updated count array is -įigure 2: Formula for updating count array Size of count is 10 (k+1, such that range of elements in A is 0 to k) Step 1: Initialize an auxiliary array, say count and store the frequency of every distinct element. Let us trace the above algorithm using an example:Ĭonsider the following input array A to be sorted.
Pictorial Representation of Counting Sort with an Example Step 6: Display B since this is the sorted array
Step 5: Add each element from input array A to B as follows: Assume that the sorted sequence is stored in an output array, say B, of size n. Step 4: The updated count array gives the index of each element of array A in the sorted sequence.
COUNTING SORTY UPDATE
Step 3: Update the count array so that element at each index, say i, is equal to. Let u be an element in A such that its frequency is stored at count. Step 2: The count/frequency of each distinct element in A is computed and stored in another array, say count, of size k+1. Also note that A can have distinct or duplicate elements These n elements have to be sorted in ascending order using the counting sort technique. Step 1: Consider an input array A having n elements in the range of 0 to k, where n and k are positive integer numbers. This sorting technique is based on the frequency/count of each element to be sorted and works using the following algorithm. Counting Sort Algorithm is an efficient sorting algorithm that can be used for sorting elements within a specific range.
0 kommentar(er)
