|
public class Sorting { private final int N = 10; private final int K = 25; private int[] A; private int[] B; private int[] C; public Sorting() { A = new int[N+1]; // not using A[0] B = new int[N+1]; // not using B[0] C = new int[K]; for (int i = 1; i < A.length; i++) A[i] = (int)(Math.random()*24 + 1); } public void printArray(int[] X, int init) { for (int i = init; i < X.length; i++) System.out.print(X[i] + " "); System.out.println(); } public void mysterySort() { for (int i = 0; i < C.length; i++) C[i] = 0; for (int j = 1; j < A.length; j++) C[A[j]] = C[A[j]] + 1; for (int i = 1; i < C.length; i++) C[i] = C[i] + C[i-1]; for (int j = A.length -1; j > 0; j--) { B[C[A[j]]] = A[j]; C[A[j]] = C[A[j]] - 1; } } public void doSort() { System.out.print("A (unsorted): "); printArray(A, 1); mysterySort(); System.out.print("B (sorted): "); printArray(B, 1); System.out.print("C: "); printArray(C, 0); } public static void main(String[] args) { Sorting sorting = new Sorting(); sorting.doSort(); } } % javac Sorting.java % java Sorting A (unsorted): 18 2 13 10 23 23 9 22 15 14 B (sorted): 2 9 10 13 14 15 18 22 23 23 C: 0 0 0 1 1 1 1 1 1 1 2 3 3 3 4 5 6 6 6 7 7 7 7 8 10The purpose of this problem is to show a completely incomprehesible algorithm, even though it looks simple. How do you suppose it works?