Home



2019/10 - DS&A #6: Bubble Sort

Hi folks,

Today we'll be looking at the Bubble Sort algorithm in our data structures and algorithms series! The Bubble Sort algorithm simply swaps nodes around, comparing them one pairing at a time and iterating through the list potentially several times, until the whole list is sorted. If we had a list of numbers like "2 1 3 4 9 5 8 6 7", then each resulting iteration of  Bubble sort would return something along these lines:

Iteration #1: 1 2 3 4 5 8 6 7 9

Iteration #2: 1 2 3 4 5 6 7 8 9

 

If we had a more "jumbled up" list, like "10 5 3 7 1", it would take a few more iterations. Mainly due to how much farther back down the list the 1 has to travel! The 10 has an easier time, because we're iterating in a direction that suits it. I'm sure there are more technical terms for these descriptions, but the ones I'm using will do for now:

Iteration #1: 5 3 7 1 10 

Iteration #2: 3 5 1 7 10 

Iteration #3: 3 1 5 7 10

Iteration #4: 1 3 5 7 10 

 

That the basic theory of the Bubble Sort, so let's take a look at some code. The below is practically boilerplate for our example. We're just saying "As long as sortArrayAndReturnTimesChange doesn't return zero, keep Bubbling!":

public class BubbleSort {
    
    public static void main(String[] args) {
         
        int[] valuesToSort = new int[args.length];
        
        for(int i = 0 ; i < args.length; i++) {
            valuesToSort[i] = Integer.valueOf(args[i]);
            System.out.print(valuesToSort[i]+",");
        }
        
        System.out.println("");
        System.out.println("***");
        
        BubbleSort bubbleSort = new BubbleSort();
        
        while(bubbleSort.sortArrayAndReturnTimesChange(valuesToSort) != 0) continue; 
            
        
        System.out.println("Sorted");
        for(int i = 0 ; i < valuesToSort.length; i++) {
            System.out.print(valuesToSort[i]+",");
        }

    }


Next we have the actual functionality. We saying that for each index we're currently on, if the current node is greater than the next one, swap them while keeping track of the number of these changes:

    public int sortArrayAndReturnTimesChange(int[] valuesToSort) {
        int timesChanged = 0;
        for(int i = 0 ; i < valuesToSort.length; i++) {
            if(i+1 <= valuesToSort.length -1 && valuesToSort[i+1] < valuesToSort[i] ) {
                timesChanged++;
                int left = valuesToSort[i];
                int right = valuesToSort[i+1];
                valuesToSort[i+1] = left;
                valuesToSort[i] = right;
                System.out.println(valuesToSort[i] + " changed places with " + valuesToSort[i+1]);
            }
        }
        System.out.println("Times changed:  " + timesChanged);
        return timesChanged;
        
    }

}

 

And that's pretty much it! The Bubble Sort is another DS&A concept that is actually quite easy to understand and implement. You'll barely use this at all in your career (Maybe in an interview), but I think it's a good idea to gain an understanding of the fundamentals that ultimately resulted in the powerful collections that we have today.

Good luck!