Counting sort is special sorting technique used to sort elements between specific range. Lets say elements belong to range 1 to K , then Counting sort can be used to sort elements in O(N) times.
Basic idea of counting sort to find number of elements less than X, so X can be put to its correct position.
When you run above program, you will get below output:
Time Complexity= O(N)
Basic idea of counting sort to find number of elements less than X, so X can be put to its correct position.
Steps for Counting Sort:
- Take an array to store count of each elements. Lets say array elements contain 1 to K then initialize count array with K.
- Now add elements of count array, so each elements store summation of its previous elements.
- Modified count array stores position of elements in actual sorted array.
- Iterate over array and put element in correct sequence based on modified count array and reduce the count by 1.
Java program for counting sort:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
package org.arpit.java2blog; import java.util.Arrays; public class CountingSortMain { public static void main(String[] args) { System.out.println("Before Sorting : "); int arr[]={1,4,7,3,4,5,6,3,4,8,6,4,4}; System.out.println(Arrays.toString(arr)); arr=countingSort(arr); System.out.println("======================="); System.out.println("After Sorting : "); System.out.println(Arrays.toString(arr)); } static int[] countingSort(int arr[]) { int n = arr.length; // The result will store sorted array int result[] = new int[n]; // Initialize count array with 9 as array contains elements from range 1 to 8. int count[] = new int[9]; for (int i=0; i<9; ++i) count[i] = 0; // store count of each element in count array for (int i=0; i<n; ++i) ++count[arr[i]]; // Change count[i] so that count[i] now contains actual // position of this element in output array for (int i=1; i<=8; ++i) count[i] += count[i-1]; for (int i = 0; i<n; ++i) { result[count[arr[i]]-1] = arr[i]; --count[arr[i]]; } return result; } } |
|
1 2 3 4 5 6 7 |
Before Sorting : [1, 4, 7, 3, 4, 5, 6, 3, 4, 8, 6, 4, 4] ======================= After Sorting : [1, 3, 3, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8] |
I would suggest to try to debug the program to understand it better.
Was this post helpful?
Let us know if you liked the post. That’s the only way we can improve.
