1. Introduction
In this tutorial, we’ll discuss the gravity sort algorithm and its single-threaded implementation in Java.
2. The Algorithm
Gravity sort is a natural sorting algorithm inspired by natural events – in this case, the force of gravity. Also known as Bead Sort, this algorithm simulates the force of gravity to sort a list of positive integers.
The idea of the algorithm is to represent positive integers using beads in vertical rods and horizontal levels – similar to an abacus, except that every level represents a single number of the input list. The next step is to drop the beads to their lowest possible position, which results in the abacus having an ascending order of the numbers:
For example, here’s the process of sorting an input list of [4, 2]:
We apply the force of gravity to the abacus. Subsequently, all beads will be at their lowest possible position after falling. The resulting state of the abacus is now an ascending order of positive integers from top to bottom.
In reality, gravity drops all the beads at the same time. However, in software, we must simulate the beads falling in different iterations. Next, we’ll look at how we can represent the abacus as a two-dimensional array, and how we can simulate the falling beads to sort the numbers of the list.
3. Implementation
To implement gravity sort in software, we’ll follow the pseudocode in this article to write the code in Java.
First, we need to transform the input list into an abacus. We’ll use a two-dimensional array to represent the rods (columns) and levels (rows) as the dimensions of the matrix. Additionally, we’ll use true or false to indicate a bead or an empty cell, respectively.
Before setting up our abacus, let’s find the dimensions of the matrix. The number of columns m equals the largest element in the list. Therefore, let’s create a method to find this number:
static int findMax(int[] A) {
int max = A[0];
for (int i = 1; i < A.length; i++) {
if (A[i] > max) {
max = A[i];
}
}
return max;
}
Now, we’re able to assign the largest number to m:
int[] A = {1, 3, 4, 2};
int m = findMax(A);
With m, we are now able to create a representation of the abacus. We’ll use the setupAbacus() method to do this:
static boolean[][] setupAbacus(int[] A, int m) {
boolean[][] abacus = new boolean[A.length][m];
for (int i = 0; i < abacus.length; i++) {
int number = A[i];
for (int j = 0; j < abacus[0].length && j < number; j++) {
abacus[A.length - 1 - i][j] = true;
}
}
return abacus;
}
The setupAbacus() method returns the initial state of the abacus. The method goes through every cell in the matrix, assigning a bead or an empty cell.
At every level in the matrix, we’ll use the ith number in list A to determine the number of beads in a row. Moreover, we iterate through every column j, and if number is greater than the jth column index, we mark this cell true to indicate a bead. Otherwise, the loop terminates early, leaving the rest of the cells empty or false in the ith row.
Let’s create the abacus:
boolean[][] abacus = setupAbacus(A, m);
We’re now ready to let gravity sort the beads by dropping them to their lowest possible positions:
static void dropBeads(boolean[][] abacus, int[] A, int m) {
for (int i = 1; i < A.length; i++) {
for (int j = m - 1; j >= 0; j--) {
if (abacus[i][j] == true) {
int x = i;
while (x > 0 && abacus[x - 1][j] == false) {
boolean temp = abacus[x - 1][j];
abacus[x - 1][j] = abacus[x][j];
abacus[x][j] = temp;
x--;
}
}
}
}
}
Initially, the dropBeads() method loops through every cell in the matrix. Starting at 1, i is the row to start with, since there won’t be any beads to drop from the bottom-most level 0. With respect to the columns, we start with j = m – 1 to start dropping the beads from right to left.
*In every iteration, we check whether the current cell, abacus[i][j], contains a bead. If so, we use a variable x to store the current level of the falling bead.* We drop the bead by decreasing x as long as it’s not the bottom-most level, and the cell below is an empty space.
Lastly, we need to transform the final state of the abacus into a sorted array. The toSortedList() method takes in the abacus as a parameter, along with the original input list, and modifies the array accordingly:
static void toSortedList(boolean[][] abacus, int[] A) {
int index = 0;
for (int i = abacus.length - 1; i >=0; i--) {
int beads = 0;
for (int j = 0; j < abacus[0].length && abacus[i][j] == true; j++) {
beads++;
}
A[index++] = beads;
}
}
We can recall that the number of beads in every row represents a single number in the list. For that reason, the method iterates through every level in the abacus, counts the beads, and assigns the value to the list. The method sets the values in ascending order starting at the highest row value. However, starting with i = 0, it places the numbers in descending order.
Let’s put all pieces of the algorithm together into a single gravitySort() method:
static void gravitySort(int[] A) {
int m = findMax(A);
boolean[][] abacus = setupAbacus(A, m);
dropBeads(abacus, A, m);
transformToList(abacus, A);
}
We can confirm the algorithm works by creating a unit test:
@Test
public void givenIntegerArray_whenSortedWithGravitySort_thenGetSortedArray() {
int[] actual = {9, 9, 100, 3, 57, 12, 3, 78, 0, 2, 2, 40, 21, 9};
int[] expected = {0, 2, 2, 3, 3, 9, 9, 9, 12, 21, 40, 57, 78, 100};
GravitySort.sort(actual);
Assert.assertArrayEquals(expected, actual);
}
4. Complexity Analysis
We saw that the gravity sort algorithm entails a lot of processing. Therefore, let’s break it down into time and space complexity.
4.1. Time Complexity
The implementation of the gravity sort algorithm starts with finding the maximum number m in the input list. This process is an O(n) runtime operation as we pass through the array once. Once we obtain m, we set up the initial state of the abacus. Because the abacus is really a matrix, visiting every cell in every row and column results in an O(m * n) operation where n is the number of rows.
Once our setup is ready, we must drop the beads to their lowest possible position in the matrix, as though gravity is affecting our abacus. Again, we’re visiting every cell in the matrix along with an inner loop that drops the beads at most n levels in every column. This process has an O(n * n * m) runtime.
Further, we must perform O(n) additional steps to recreate our list based on the sorted representation in the abacus.
Overall, gravity sort is an O(n * n * m) algorithm, considering its effort to simulate the beads falling.
4.2. Space Complexity
The space complexity for gravity sort is proportional to the size of the input list and its largest number. For example, a list with n number of elements and a maximum number m requires a matrix representation of n x m dimensions. Consequently, the space complexity is O(n * m) to allocate extra space in memory for the matrix.
Nonetheless, we try to minimize the space complexity by representing beads and empty cells with single bits or numbers. Namely, 1 or true indicates a bead, and similarly, a 0 or false value is an empty cell.
5. Conclusion
In this article, we learned how to implement a single-threaded approach for the gravity sort algorithm. Also called bead sort, this algorithm is inspired by the force of gravity naturally sorting positive integers that we represent as beads in an abacus. Yet, in software, we use a two-dimensional matrix and single-bit values to reproduce this environment.
Although the single-threaded implementation has a costly time and space complexity, this algorithm performs well in hardware and multi-threaded applications. Nonetheless, the gravity sort algorithm exemplifies how natural events can inspire solutions to software implementations.
As always, the code for the implementation of this algorithm can be found over on GitHub.