BubbleSort

 Because it’s so simple, BubbleSort is one of the first sorting algorithms anyone learns. However, it does have its drawbacks, most notably its slow speed.

Imagine we have an array as shown here, assumed not to be sorted:

3

7

1

6

5

2

4

And we want the array sorted in ascending order, ending up as

1

2

3

4

5

6

7

We can, in a sense, “bubble” each item up or down into position, making a pass through potentially the whole array to get the number in the right position:

Let’s do that process to get 1 in place:

3

7

1

6

5

2

4

Is 1 in the right spot? No, it’s too far to the right.

3

1

7

6

5

2

4

Is 1 in the right spot? No, it’s too far to the right.

1

3

7

6

5

2

4

Is 1 in the right spot? Yes. It has bubbled up.

Now we need 2:

1	3	7	6	5	2	4
1	3	7	6	2	5	4
1	3	7	2	6	5	4
1	3	2	7	6	5	4
1	2	3	7	6	5	4

3 happens to be in the right place

Now we bubble up 4:

1	2	3	7	6	5	4
1	2	3	7	6	4	5
1	2	3	7	4	6	5
1	2	3	4	7	6	5

 

And the process continues, until, with all these pairwise comparisons and swaps, the list is in the proper order, the numbers having gradually risen into position like bubbles in a soda.

The worst possible outcome for this sort occurs when the list is already sorted, but in the opposite order. What happens if we want 123…7 but have 765…1?:

7	6	5	4	3	2	1
7	6	5	4	3	1	2
7	6	5	4	1	3	2
7	6	5	1	4	3	2
7	6	1	5	4	3	2
7	1	6	5	4	3	2
1	7	6	5	4	3	2

And all this work was just to bubble up the 1—we now have to do all this over again to bubble up the 2, 3, 4, 5, 6, and 7.