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.
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; } } |
When you run above program, you will get below output:
|
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] |
Time Complexity= O(N)
I would suggest to try to debug the program to understand it better.
