Gravity/Bead Sort in Java

1. Introduction

In this tutorial, we will discuss the Gravity Sort algorithm and its single-threaded implementation in Java.

2. Algorithm

Gravitational sorting is a natural sorting algorithm inspired by natural phenomena—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 vertical rods and beads in horizontal levels. – Similar to abacus, except that each level represents the same number of input lists. The next step is to drop the beads into their lowest possible position, resulting in an ascending sequence of numbers in the abacus:

For example, here is the process of sorting the input list [4, 2],

We apply gravitational force on the abacus. LaterAll the beads will be in their lowest possible position after falling, The resulting position of the abacus is now an ascending sequence of positive integers from top to bottom.

In fact, gravity causes all the beads to drop at the same time. However, in software, we must simulate beads falling in different iterations. Next, we’ll see how we can represent the abacus as a two-dimensional array, and how we can simulate falling beads to sort the numbers in the list.

3. Implementation

To implement Gravity Sort in software, we will follow the pseudocode in this article to write the code in Java.

First, we need to convert the input list to abacus. We will use a two-dimensional array to represent the rods (columns) and levels (rows) as the dimensions of the matrix. Additionally, we will use Truth either false to indicate a bead or an empty cell, respectively.

Before setting up our abacus, let’s find the dimensions of the matrix. number of columns M Equals to the largest element in the list. So, 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 are able to assign the largest number M,

int[] A = {1, 3, 4, 2};
int m = findMax(A);

with M, Now we are able to represent the abacus. we will use setup abacus() How 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;
}

setup abacus() The method returns the initial state of the abacus. The method goes through each cell in the matrix, specifying a bead or an empty cell.

At each level in the matrix, we will use Ith number in the list a To determine the number of beads in a row. Also we iterate through every column Jayand if number is greater than Jayth column index, we mark this cell Truth To indicate a bead. Otherwise, the loop terminates early, leaving the remaining cells blank or false In IThrow.

Let’s make an abacus:

boolean[][] abacus = setupAbacus(A, m);

Now we are ready to let gravity sort the beads by dropping them to their lowest possible position,

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--;
                }
            }
        }
    }
}

in the beginning, dropbeads() The method loops through each cell in the matrix. starting from 1, I The row is to begin with, as there will be no beads to fall from the bottom-most level 0. With respect to the column, we start with J = M – 1 To start drop the beads from right to left.

In each iteration, we check whether the current cell, Abacus[i][j], a bead is included. If so, we use a variable x To store the current level of the falling bead. we drop the bead down x Unless it is the lowest level, and the bottom cell is a blank space.

Finally, we need to convert the last position of the abacus into a sorted array. sorted list() The method takes the abacus with the original input list as a parameter, 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 remember that the number of beads in each row represents the same number in the list. For this reason, the method iterates through each level in the abacus, counts the beads, and assigns values ​​to the list. Method sets values ​​in ascending order starting with the highest row value, However, the beginning I = 0, IT Sorts the numbers in descending order.

Let’s put all the pieces of the algorithm together 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 verify the working of the algorithm 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 requires a lot of processing. So, let’s break it down into the complexity of time and space.

4.1. time complexity

The implementation of the gravity sort algorithm begins with finding the maximum number M Input list. this process a Feather) As a runtime operation we go through the array once. once we get M, we determine the initial state of the abacus. Because the abacus is actually a matrix, visiting each cell in each row and column will result in a O(m*n) operation where n is the number of rows.

Once our setup is ready, we should leave the beads in their lowest possible position in the matrix, as if gravity were affecting our abacus. Again, we are visiting each cell in the matrix as well as an inner loop that drops the beads more and more n level in each column. This process is one O(n * n * m) runtime.

In addition, we must perform Feather) Additional steps to reconstruct our list based on the sorted representation in the abacus.

Overall, the gravity type is a O(n * n * m) The algorithm is considering its attempt to simulate falling beads.

4.2. space complexity

The space complexity for the 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 maximum number M requires matrix representation of nxm Dimensions. consequently, space complexity is O(n*m) To allocate extra space in memory for the matrix.

Nonetheless, we try to reduce the space complexity by presenting the beads and empty cells with single bits or numbers. that is, 1 either Truth indicates a bead, and so on, a 0 either false value is an empty cell.

5. Epilogue

In this article, we learned how to implement a single-threaded approach to the gravity sort algorithm. Also called bead sort, this algorithm is inspired by the force of gravity to naturally sort positive integers that we represent as beads in the abacus. Nevertheless, in software, we use two-dimensional matrices and single-bit values ​​to reproduce this environment.

Although single-threaded implementation has a costly time and space complexity, this algorithm performs well in hardware and in multi-threaded applications. Nonetheless, the Gravity Sort algorithm exemplifies how natural phenomena can inspire solutions for software implementations.

As always, the code for the implementation of this algorithm can be found on GitHub.

       

Leave a Comment