The indefatigable Bubble Sort is beloved by her whole family, provided she isn't in the room.  

The eight-year-old daughter of Heap Sort and Cocktail Shaker Sort, she absolutely loves to tell you all about her day: what things she ate, this cool car she saw on the way over, how her little brother is annoying her at that particular moment, what she wants for her birthday in eight months. Everything.

Chloe
Photo by Edward Cisneros / Unsplash

Her parents adore her, but sometimes the family wishes she would just shut up for five minutes. All except for grandma Merge Sort, who could listen to little Bubbly's stories and exclamations for days. No wonder she loves going to Grandma's house.

The Rundown

exceptionnotfound/SortExtravaganzaCSharp
Lots of example sorting algorithms, from a family reunion. - exceptionnotfound/SortExtravaganzaCSharp
GitHubexceptionnotfound

Algorithm

  1. FOR each item in the collection
  2. IF two adjoining elements are in the wrong order, SWAP them.
  3. GO TO 1, CONTINUE until the list is sorted.

Visualization

Animation used under license

This animation is a good example of Bubble Sort, because like Bubble Sort it takes FOREVER to get anything done. So let's try to build our own example.

Say we have the following collection:

{ 5, 8, 2, 4, 1 }

Bubble sort will swap elements on each pass that are not in the correct order. Here's the position of the collection elements after each swap:

{ 5, 2, 8, 4, 1 }
{ 5, 2, 4, 8, 1 }
{ 5, 2, 4, 1, 8 }
{ 2, 5, 4, 1, 8 }
{ 2, 4, 5, 1, 8 }
{ 2, 4, 1, 5, 8 }
{ 2, 1, 4, 5, 8 }
{ 1, 2, 4, 5, 8 }

In order to do this sort, the algorithm has to complete 4 passes of the array in order to sort 5 elements. That's wildly inefficient...

...But cool to watch.  Check out this "audibilization" from YouTube:

C# Implementation

class BubbleSort
{
    public static void Main(string[] args)
    {
        int[] array = { 92, 28, 3, 71, 50, 14, 24, 20, 66, 70, 45, 17, 9, 99, 38 };
        int temp;
        Console.WriteLine("Bubble Sort");
        CommonFunctions.PrintInitial(array);
        //1. For each item in the array...
        for (int i = 0; i <= array.Length - 2; i++)
        {
            for (int j = 0; j <= array.Length - 2; j++)
            {
                //2. ...if two adjoining elements 
                //   are in the wrong order, swap them.
                if (array[j] > array[j + 1])
                {
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
                //3. Repeat this for all pairs of elements.
            }
        }
        CommonFunctions.PrintFinal(array);
        Console.ReadLine();
    }
}

Time and Space Complexity

Bubble Sort is, to put it frankly, the worst sorting algorithm that isn't trying to be bad.

The best-case scenario is still O(n2). It is inefficient, slow, and generally a poor-performing sort, despite how easy the algorithm is to implement. That simplicity is really this algorithm's only redeeming value: it's easy to teach, in a "this is what you should not do" sort of way.  

In short, Bubble Sort should not be used for real-world sorting scenarios.

Summary

Bubble Sort is a highly inefficient sorting algorithm that traverses through a collection, swapping neighboring values if they are out of order. It has an implementation only a mother could love. Or, perhaps, a grandmother?

Bubble's elder sister Odd-Even Sort is next, and watch out; she's a master at getting someone to give her extra ice cream.

Odd-Even Sort in C#
Odd-Even Sort is a headstrong little girl. The middle daughter of Heap Sort and Cocktail Shaker Sort, she has recentlydiscovered she a particular skill, a skill that makes her a nightmare to peoplelike her parents. This skill has allowed her to get extra dessert, more screentime, even less chor…
Exception Not FoundMatthew Jones

Don't forget to check out the sample project over on GitHub!

Happy Coding!