Skip to content

Instantly share code, notes, and snippets.

@cciollaro
Created October 5, 2013 22:55
Show Gist options
  • Save cciollaro/6847040 to your computer and use it in GitHub Desktop.
Save cciollaro/6847040 to your computer and use it in GitHub Desktop.
stable counting sort in java
public class CountingSort{
public static void main(String[] args){
int[] a = {5,6,7,1,2,4,5,6,1,0,3,4,2};
printArray(countingSort(a, 7));
}
public static int[] countingSort(int[] a, int k){
int[] b = new int[a.length];
int[] c = new int[k + 1];
for(int i = 0; i < a.length; i++)
c[a[i]] = c[a[i]] + 1;
for(int i = 1; i < c.length; i++)
c[i] = c[i] + c[i-1];
printArray(a);
printArray(b);
printArray(c);
for(int i = a.length - 1; i >= 0; i--){
b[ c[a[i]]-1 ] = a[i];
c[a[i]] = c[a[i]] - 1;
}
return b;
}
public static void printArray(int[] a){
for(int x: a){
System.out.print(x + " ");
}
System.out.println("");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment