Skip to content

Instantly share code, notes, and snippets.

@djhworld
Created March 27, 2016 13:09
Show Gist options
  • Save djhworld/b10e15d891b424ead3ed to your computer and use it in GitHub Desktop.
Save djhworld/b10e15d891b424ead3ed to your computer and use it in GitHub Desktop.
public class BeadSort {
private static final int BEAD = 1;
public void sort(int[] array) {
int[][] abacus = populateAbacusAndWipeInput(array);
for (int pole = 0; pole < abacus[0].length; pole++) {
int poleRow = abacus.length - 1;
for (int currentRow = poleRow; currentRow >= 0; currentRow--) {
if (abacus[currentRow][pole] == BEAD) {
array[poleRow] += 1; //increment as this row has 1 bead on the pole
poleRow--;
}
}
}
}
private int[][] populateAbacusAndWipeInput(int[] array) {
int rowsRequired = array.length;
int polesRequired = getMax(array);
int[][] abacus = new int[rowsRequired][polesRequired];
for (int row = 0; row < abacus.length; row++) {
int itemToPlaceOnAbacus = array[row];
for (int pole = 0; pole < itemToPlaceOnAbacus; pole++) {
abacus[row][pole] = BEAD;
}
array[row] = 0; // wipe out element
}
return abacus;
}
private int getMax(int[] arr) {
int max = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max)
max = arr[i];
}
return max;
}
}
@djhworld
Copy link
Author

This is O(S)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment