Skip to content

Instantly share code, notes, and snippets.

@zcwang
Created March 28, 2018 02:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save zcwang/3db722278f177c4b0b47f45e5aacad69 to your computer and use it in GitHub Desktop.
Save zcwang/3db722278f177c4b0b47f45e5aacad69 to your computer and use it in GitHub Desktop.
Good counting sort for reference
public class CountingSort {
static int[] countingSort(int arr[]) {
int[] aux = new int[arr.length];
int min = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
} else if (arr[i] > max) {
max = arr[i];
}
}
int[] count_list = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
count_list[arr[i] - min]++;
}
count_list[0]--;
for (int i = 1; i < count_list.length; i++) {
count_list[i] = count_list[i] + count_list[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
aux[count_list[arr[i] - min]] = arr[i];
count_list[arr[i] - min]--;
}
return aux;
}
static void print(int arr[], int n) {
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String[] args) {
int[] unsorted = {
5,
3,
12,
2,
4,
1,
99,
5,
2,
3,
1,
4
};
print(unsorted, unsorted.length);
int[] sorted = countingSort(unsorted);
print(sorted, sorted.length);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment