|
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 10
The purpose of this problem is to show a completely incomprehesible
algorithm, even though it looks simple. How do you suppose it works?