@Test public void testCountingSort() { int[] arr = new int[] { 17, 3, 99, 51 }; Integer[] expected = { 3, 17, 51, 99 }; Integer[] actual = Sorter.countingSort(arr); Assert.assertArrayEquals(expected, actual); }
public static Integer[] countingSort(final int[] arr) { final Map<Integer, Pair> countMap = new HashMap<>(); for (final int i : arr) { Pair p = new Pair(i, 1); if (countMap.containsKey(i)) { p.value += countMap.get(i).value; } countMap.put(i, p); } BinarySearchTree<Pair> bst = new BinarySearchTree<>(countMap.values()); final List<Pair> sortedPairs = BinaryTreeWalker.recursiveInorder(bst.root()); return CollectionUtils.collect(sortedPairs, TransformerUtils.<Pair, Integer> invokerTransformer("getKey")) .toArray(new Integer[] {}); }
Sorter { public static Integer[] countingSort(final int[] arr) { final Map<Integer, Pair> countMap = new HashMap<>(); for (final int i : arr) { Pair p = new Pair(i, 1); if (countMap.containsKey(i)) { p.value += countMap.get(i).value; } countMap.put(i, p); } BinarySearchTree<Pair> bst = new BinarySearchTree<>(countMap.values()); final List<Pair> sortedPairs = BinaryTreeWalker.recursiveInorder(bst.root()); return CollectionUtils.collect(sortedPairs, TransformerUtils.<Pair, Integer> invokerTransformer("getKey")) .toArray(new Integer[] {}); } }
Sorter { public static Integer[] countingSort(final int[] arr) { final Map<Integer, Pair> countMap = new HashMap<>(); for (final int i : arr) { Pair p = new Pair(i, 1); if (countMap.containsKey(i)) { p.value += countMap.get(i).value; } countMap.put(i, p); } BinarySearchTree<Pair> bst = new BinarySearchTree<>(countMap.values()); final List<Pair> sortedPairs = BinaryTreeWalker.recursiveInorder(bst.root()); return CollectionUtils.collect(sortedPairs, TransformerUtils.<Pair, Integer> invokerTransformer("getKey")) .toArray(new Integer[] {}); }  }
Sorter { public static Integer[] countingSort(final int[] arr) { final Map<Integer, Pair> countMap = new HashMap<>(); for (final int i : arr) { Pair p = new Pair(i, 1); if (countMap.containsKey(i)) { p.value += countMap.get(i).value; } countMap.put(i, p); } BinarySearchTree<Pair> bst = new BinarySearchTree<>(countMap.values()); final List<Pair> sortedPairs = BinaryTreeWalker.recursiveInorder(bst.root()); return CollectionUtils.collect(sortedPairs, TransformerUtils.<Pair, Integer> invokerTransformer("getKey")) .toArray(new Integer[] {}); }  static int[] mergeSort(int[] arr); static int[] quickSort(int[] arr); static int[] bucketSort(int[] arr); static Integer[] countingSort(final int[] arr); }
Sorter { public static Integer[] countingSort(final int[] arr) { final Map<Integer, Pair> countMap = new HashMap<>(); for (final int i : arr) { Pair p = new Pair(i, 1); if (countMap.containsKey(i)) { p.value += countMap.get(i).value; } countMap.put(i, p); } BinarySearchTree<Pair> bst = new BinarySearchTree<>(countMap.values()); final List<Pair> sortedPairs = BinaryTreeWalker.recursiveInorder(bst.root()); return CollectionUtils.collect(sortedPairs, TransformerUtils.<Pair, Integer> invokerTransformer("getKey")) .toArray(new Integer[] {}); }  static int[] mergeSort(int[] arr); static int[] quickSort(int[] arr); static int[] bucketSort(int[] arr); static Integer[] countingSort(final int[] arr);  }