# Bubble Sort - The Sorting Algorithm Family Reunion

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.

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

**Created By:**Unknown (Popularized by Donald Knuth)**Type:**Exchange**Stable?**Yes**Best-Case:***O(n*^{2})**Average-Case:***O(n*^{2})**Worst-Case:***O(n*^{2})**Space Complexity:***O(n)***Sample Project:**Over on GitHub

### Algorithm

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

### Visualization

This animation is a good example of Bubble Sort, because like Bubble Sort it takes FOREVER to get anything done. So let's try another 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:

### 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(n^{2}). 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?

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

Happy Coding!