How To Sort Characters In A Word – Bubble Sort Algorithm In Java

Algorithms are an important part of software engineering industry. They become more and more used during interviews. They are maybe even more used during interviews than during the real jobs. You can find testimonials of different people around the world about interviewers asking them to solve a problem using an algorithm. In some cases, you will get a coding challenge while in others you can get a question as a real world example. So I would like to show you here how to solve one of common interview questions. How to sort any word in programmatic way using bubble sort algorithm in Java.

The choice of tools

I have chosen to do this assignment with Java, because Javascript has a built-in sort function and it is not interesting. Second, Java seems like the most used language among QA engineers. In general, during the interview you will be allowed to choose any language you like. The assignment can be done with any programming language.

What is bubble sort algorithm?

This type of algorithm is used to compare two items at a time and swap their places if the certain condition is met. In the picture below I compare the adjacent letters in my name. Then I move the letter R in front of U to rearrange them alphabetically.

In the next step this algorithm would compare U which is in second place now and O in the third place. It would apply the same logic as before. O would move in front of U. Then O, now in second place would be compared to R in the first place. O would move in front of R. Then we would continue to perform the same logic until all the letters get sorted. This algorithm grows exponentially. This means that the number of maximum combinations is n² where n is the number letters. This is why it is not very effective, because a small change adds a large number of additional operations.

Understanding the problem

The first thing we need to do when we get such assignment is to read it thoroughly and ask questions if there is something vague or unclear. Let’s say that the assignment is simple enough. Just to sort your first and last name. Since we understand that we will need to create a sorter of some kind, we can be sure that we need to use one of the sorting algorithms. In this case we can solve the problem using bubble sort algorithm in Java. This is a very slow algorithm and its complexity is too high to be used in real life, but for the sake of this assignment we can use it.

First steps

At first we need to create a class to contain the methods for comparing the two letters and swapping them. Let’s call this class BubbleSorter. We will add a constructor in this class to initialize the comparator. Java has Comparator interface in java.util.Comparator package which we can use in this assignment.

public class BubbleSorter {
    private final Comparator _comparator;

    public BubbleSorter(Comparator comparator) {
        this._comparator = comparator;
    }
}

The sort method

In the next step we need to create sort method which will compare two letters and swap them if necessary. We do this in the same BubbleSorter class.

//add at the top of the class import java.util.List;

public List sort(List sortableList) {
        int size = sortableList.size();
        for(int charIndex = 1; charIndex < size; charIndex++) {
            for(int leftElementIndex = 0; leftElementIndex < (size - charIndex); leftElementIndex++) {
                int rightElementIndex = leftElementIndex + 1;
                if(_comparator.compare(sortableList.get(leftElementIndex), sortableList.get(rightElementIndex)) > 0) {
                    swap(sortableList, leftElementIndex, rightElementIndex);
                }
            }
        }
        return sortableList;
    }

This sort method will receive a List of characters which need to be sorted. Next we record the number of the elements in the lists and store this information in size variable. Now, we have two nested for loops. The first for loop iterates through the list of the letters. Note that the charIndex starts from 1. This is because we start comparison from the letter with index 1. Start from 0 wouldn’t make sense because the letter with 0 index doesn’t have anything to the left of it.

Second for loop should make sure that the every letter is moved to the left side as much as possible. If we didn’t have the second for loop the comparison would run only one time. Remember the picture above? Remember how the letter O should first move in front of letter U but then also in front of letter R in the next iteration. Without the second loop letter O would move just once and it would end up in the wrong position in the end.

The rightElementIndex is leftElementIndex plus 1, which is logical. Now, in the next line we use in-built compare method from Comparator interface. We will implement this method later. We pass two arguments to this method representing elements from the list. Get method in sortableList.get helps us find a specific element in position specified by index.

The swap method

In the above example if left element is greater than the right the result of comparison would be greater than 0. This would fulfill the condition and the swap method would be called. In this method we pass three arguments: the entire list of letters, left element index and right element index. This method is also added in BubbleSorter class.

private void swap(List list, int leftIndex, int rightIndex) {
        Object temp = list.get(leftIndex);
        list.set(leftIndex, list.get(rightIndex));
        list.set(rightIndex, temp);
    }

First, we create a temp object where we will temporarily store the left so we don’t lose it. Then we will replace the left element with the right element in the original list. Finally, we add the former left element from temp object to the position of right element.

The main class

We will add Main class in Java which should include main method. In the main method, we need to implement compare method which we used in sort method above.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Comparator comparator = new Comparator() {
            @Override
            public int compare(Object firstObject, Object secondObject) {
                int left = (Character) firstObject;
                int right = (Character) secondObject;
                if (left > right) {
                    return 1;
                } else if (left < right) {
                    return -1;
                }
                return 0;
            }
        };
}

The compare method has two arguments in its signature which are of type object. Since we are working with chars, we need to cast the objects to Character type and we store those values as left and right respectively. Now, we add conditional logic to return 1 if left element is greater than the right, and -1 vice versa. If they are equal we will return 0. The operators in this conditional logic make difference if you want to sort the characters in ascending or descending order. In the way as it is written above the characters will be sorted in ascending order. If we swap the operators in if and else if they will be sorted in descending order. Or alternatively, you can replace the return values which should do the same.

Breaking the string into array of characters

Our assignment is to sort the letters from our first and last name, but this will be written as a string. We need to break that string into characters and add them to an array.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Comparator comparator = new Comparator() {
            @Override
            public int compare(Object firstObject, Object secondObject) {
                int left = (Character) firstObject;
                int right = (Character) secondObject;
                if (left > right) {
                    return 1;
                } else if (left < right) {
                    return -1;
                }
                return 0;
            }
        };
        BubbleSorter sorter = new BubbleSorter(comparator);

        String name = "urossimic";
        List<Character> listOfChars = new ArrayList<>();
        for(int i = 0; i < name.length(); i++) {
            listOfChars.add(name.charAt(i));
        }
        System.out.println(sorter.sort(listOfChars));
    }
}

My string is added and then I create a new instance of ArrayList where I would store the characters. Then I create a new loop to iterate through the string and add each of the characters to the ArrayList. In the end I print the result of the sorting algorithm.

I finally created the new instance of BubbleSorter class (highlighted in green) and I pass the comparator object. The result is below. I hope you enjoyed my explanation of bubble sort algorithm in Java and that it was easy to follow. If you need more practice for your interview visit my testing challenges page.