I enjoy coding sorting algorithms (merge sort, insertion sort, selection sort, quicksort), so I was excited to see that Day 20 of HackerRank's 30 Days of Code was to write Bubble sort. I have written Bubble sort in Python numerous times and meant to write an article on it, but there are so many cool things I am learning now that it got pushed on the backburner. Today is the day, however, that I not only mention Bubble sort, but also mention HackerRank in case you haven't heard of it before.

Bubble Sort in Python

Bubble sort compares adjacent items in a list and swaps them when necessary so they are in ascending order. Lower values slowly move to the front of the list while larger numbers move to the back of the list. Its runtime performance is O(n2), which makes it impractical for large values of n. It is a fun sorting algorithm to code, however. Here is my implementation of Bubble sort in Python that I submitted to HackerRank.

def bubble_sort(lst):
    num_swaps = 0

    if len(lst) < 2:
        return num_swaps

    for i in range(len(lst) - 1, 0, -1):
        for j in range(i):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
                num_swaps += 1

    return num_swaps

a = list(range(3, 0, -1))
swaps = bubble_sort(a)

print('Array is sorted in {0} swaps.'.format(swaps))
print('First Element: {0}'.format(a[0]))
print('Last Element: {0}'.format(a[-1]))

A couple of notes about my version of Bubble sort, since I suspect people code it differently.

Keeping Track of Swaps in Bubble Sort

My implentation of Bubble sort sorts in-place and returns the number of swaps. Keeping track of the number of swaps was a requirement of the HackerRank sorting challenge. One could easily remove the variable num_swaps from the code if you don't care about the number of swaps.

Limiting the Number of Subsequent Passes in the List

After each pass in Bubble sort the next highest value is in its proper position in the list. For example, after the first pass, the highest value is at the end of the list. After the second pass, the second highest value is in the next to the last position in the list. And so on, and so forth. This means you do not have to keep checking the items at the end, because they are in their proper position. Therefore, the inner loop in my code gradually gets smaller and smaller with each pass because it no longer needs to check the items at the end of the list. After each pass it reduces the number of items it checks by 1 as you can see from the double for loop.

for i in range(len(lst) - 1, 0, -1):
    for j in range(i):

This isn't really necessary, but I added the performance tweak because it makes sense. I don't see this performance enhancement in all Bubble sort code samples.

HackerRank 30 Days of Code Challenge

As I have mentioned several times, I am learning Python as well as computer science, algorithms, data structures, and a bunch of other topics in the majority of my free time. I came across HackerRank and similar websites that offer various programming challenges to help developers write better code. There is a lot to HackerRank and I have only scratched the surface, but approximately 3 weeks ago I joined the 30 Days of Code Challenge and promised myself I would complete it using Python 3. However, not all challenges are available in all languages, so I've been solving a few of the challenges using C#.

Each day I receive an email from HackerRank mentioning a new challenge. Day 20 is the Bubble sort challenge. I get a nice description of the challenge along with supplement information and expected input, output, and possibly starter code.

I typically write the solutions in PyCharm on my MacBook Pro or Pythonista on my iPad Pro before submitting the answer on HackerRank. All of the challenges have been easy, yet interesting, taking no more than 30 minutes and most taking half that time. I've written Bubble sort before, so it took about 15 minutes to solve.

HackerRank has a nice editor for one to enter the code. For me, I typically copy-and-paste the code from PyCharm or Pythonista.

Bubble Sort in Python from HackerRank 30 Days of Code

I ran the Bubble sort code against HackerRank's simple test cases and it passed. Once I submit the code it will be run against additional test cases. I get 30 points for the submission when the Bubble sort code passes all the tests.

HackerRank Programming Challenge Solved

HackerRank's 30 Days of Code Challenge is just one of many challenges. I want to complete this challenge before moving to another one, but there are challenges on algorithms ( which I am personally excited about ) as well as data structures, artificial intelligence, mathematics, Python, SQL, datatabase, functional programming, etc. There are also contests that happen from time-to-time. It's a great way to learn and stay sharp. I am enjoying my experience thus far, and I look forward to future challenges.

Bubble Sort in C#

If you are a C# developer or just interested in C#, I also wrote an example of Bubble Sort in C#.

using System;


public int BubbleSort(int[] lst) {
    var numSwaps = 0;
    
    if (lst.Length < 2)
        return numSwaps;
        
    for (int i = lst.Length - 1; i > 0; i--)
    for (int j = 0; j < i; j++) {
        if (lst[j] > lst[j+1]) {
            var temp = lst[j+1];
            lst[j+1] = lst[j];
            lst[j] = temp;
            numSwaps++;
        }
    }
    
    return numSwaps;
}

var lst = new [] {3, 2, 1};
var swaps = BubbleSort(lst);

Console.WriteLine("sorted list = {0}", string.Join(",", lst));
Console.WriteLine($"swaps = {swaps}");

I wrote Bubble Sort in C# using my iPad Pro and the continous C# and F# IDE. If you like to challenge yourself at writing C# or F# and have an iPad, I highly recommend the continuous C# and F# IDE for practicing C# and F# coding when the opportunity may rise.

Bubble Sort in C#

Comb Sort

There are a few sorting algorithms that attempt to improve the efficiency of bubble sort. One of them is Comb Sort, which improves bubble sort by eliminating turtles. Turtles are small values at the end of the unsorted list that slowly make their way to the front of the list. For more information on Comb Sort, read my article: Comb Sort Improves Bubble Sort by Eliminating Turtles.

Cocktail Sort

Just like comb sort, cocktail sort is another sorting algorithm that attempts to improve the efficiency of bubble sort by eliminating turtles. Bubble sort continually bubbles large values to the end of the list from left-to-right on each pass. Cocktail sort uses a bidirectional method that bubbles large values to the end of the list on one pass and small values to the front of the list on the next pass. For more information on cocktail sort, read my article: Cocktail Sort.

You can find me on twitter as @KoderDojo.

Posted by Koder Dojo

I am a freelance, C# ASP.NET MVC Developer learning Python as well as computer science, algorithms, data structures, and data science. In addition, I am learning and developing with the new Microsoft ASP.NET Core MVC and EF Core so you will see numerous tutorials and examples of ASP.NET Core on my website. I will also be sharing my adventures on websites that offer programming challenges, like HackerRank, to encourage other developers to learn new coding skills. You can find me on twitter as @KoderDojo. Best Wishes!

Related Posts: