What is bubble sort?

Answer 1

Bubble sort is a sorting algorithm that compares 2 adjacent items at a time, starting from the beginning of a list, and swapping them if they are out of sequence. Each comparison gradually moves the largest item to the end of the list (likened to a bubble making its way to the surface of water). After n*n passes, all the items will be sorted. The big O for a standard bubble sort is therefore O(n*n).

The algorithm can be improved somewhat. Since it is clear that the last item is sorted on each pass, the unsorted set can be reduced by 1 element on each pass. Moreover, since the final swap on each pass indicates that everything from that point on is already sorted, the unsorted set can often be reduced by more than 1 element on each pass. For an already sorted list, the worst case is reduced to O(n), constant time.

For small sets of data, perhaps 10 to 20 items, the bubble sort is reasonably efficient, especially on partially sorted lists. However the insert sort algorithm offers similar or better performance on average. With larger sets, the quick sort algorithm is hard to beat, but is let down by inefficiencies when dealing with partially sorted lists. Hybrid sorts can improve things a little, however, there is no efficient way to check the state of a list to determine the most efficient algorithm to use at any given point.

Answer 2

A bubble sort works by comparing consecutive pairs of elements in your data, switching their order if necessary. An example will likely make the previous sentence make sense...

Let's say we want to sort the following length-5 array in ascending (low-high) order.

array - original

0: 1

1: 3

2: 2

3: 5

4: 0

5: 4

A bubble sort consists of a series of "passes." During each pass, each pair of elements will be compared. If they are in the wrong order (the higher one comes first) then we must switch them. Following is the first pass of sorting:

compare positions (0,1)

array[0] = 1, array[1] = 3

their order is correct, so do not switch them

compare positions (1,2)

array[1] = 3, array[2] = 2

their order is incorrect, so switch them

array[1] = 2, array[2] = 3

compare positions (2,3)

array[2] = 3, array[3] = 5

their order is correct, so do not switch them

compare positions (3,4)

array[3] = 5, array[4] = 0

their order is incorrect, so switch them

array[3] = 0, array[4] = 5

compare positions (4,5)

array[4] = 5, array[5] = 4

their order is incorrect, so switch them

array[4] = 4, array[5] = 5

So at the end of our first pass:

array - after one pass

0: 1

1: 2

2: 3

3: 0

4: 4

5: 5

Notice how the largest value (5) moved all the way to the end, where it should be. No matter the configuration of the original values, the first pass will always guarantee that the largest value will "bubble up" to the top position in the array. In the worst-case scenario, a bubble sort on an array of size n will take n comparisons over n-1 passes to be completely sorted (O(n2) for a worst-case scenario).

Now let's do a few more passes. I'll skip the lengthy explanation and show just the end results of each pass.

array - after two passes

0: 1

1: 2

2: 0

3: 3

4: 4

5: 5

array - after three passes

0: 1

1: 0

2: 2

3: 3

4: 4

5: 5

array - after four passes

0: 0

1: 1

2: 2

3: 3

4: 4

5: 5

And now we see that our array is nicely sorted. Remember the worst-case scenario should take n-1 passes. This was one of those examples. But let's say that we didn't know how many passes it should take. How would we know when the bubble sort is finished?

The bubble sort algorithm comes with a nice little feature that tells us that if we make no changes on a pass, then the data is sorted. This allows us to stop our algorithm on the exact pass that has the data sorted. What it also means is that if some pre-sorted data is fed into a bubble sort implementation, it should take only a single pass to figure out that the data is sorted. So our best-case scenario is O(n) (n comparisons during 1 pass).

(See the related questions for a generic Java-style implementation)

Answer 3

Bubble sorting is a primitive sorting algorithm. It is never used in production code because it is an inherently inefficient algorithm with no practical applications. Its primary purpose is to educate new programmers in the design of efficient algorithms (or how not to write an algorithm).

In pseudocode, the bubble sort algorithm can be implemented as follows (using a 0-based array):

procedure bubblesort (A : list of sortable items)

n := length(A)

repeat

swapped := false

for i := 1 to n-1 inclusive do

if A[i-1] > A[i] then

swap (A[i-1], A[i])

swapped := true

end if

end for

until swapped=false

end procedure

As we can see, the algorithm is formed from two loops, one nested inside the other. The outer loop repeats so long as at least one swap operation occurs within the inner loop. The inner loop traverses the entire array from the second element to the last element. On each iteration of the inner loop, we compare the current element with the one that precedes it, swapping them if they are out of sequence (and setting a flag to denote that a swap occurred).

The problem with this implementation is that for an array of n elements we end up performing n-1 comparisons on every iteration of the outer loop. The best case occurs when there are no swaps in the first iteration of the outer loop, thus there will be n-1 comparisons in total. But this can only happen when the array is already sorted. However, if the array is in reverse order we end up with the worst case of n-1 iterations of the outer loop and therefore (n-1)*(n-1) comparisons in total. Even if only one element were out of sequence, we'd incur 2*(n-1) comparisons.

We typically denote an algorithm's complexity using big-O notation, where O(1) is constant time and is the best we can ever hope to achieve. There is no sorting algorithm that can achieve this -- all are expressed in terms of the number of elements, n. In this case we have a best case of O(n) and a worst case of O(n squared). Note that we do not use n-1 in big-O notation, even though that would be closer to the true complexity. The main reason for this is that as well as comparison operations there may also be swap operations and although each operation can be done in constant time, they won't always correlate. Therefore big-O is merely an approximation of the complexity.

Given that the nth iteration of the outer loop places the nth element in its correct position, every element from the nth to the last must therefore be in its correct place -- yet the algorithm continues to compare these elements on subsequent iterations of the outer loop. To avoid this we need to make a slight alteration to the algorithm which reduces the number of elements (n) upon each iteration of the outer loop:

procedure bubblesort (A : list of sortable items)

n := length (A)

repeat

swapped := false

for i := 1 to n-1 inclusive do

if A[i-1] > A[i] then

swap (A[i-1], A[i])

swapped := true

end if

end for

n := n - 1

until not swapped

end procedure

Now the worst case is reduced to O(n triangular). A triangular number is the sum of all the values 1 to n. While this improves the worst case by eliminating around 50% of the comparisons, it doesn't improve the general case. We can see that upon each iteration of the outer loop, the last element swapped in the inner loop tells us that everything from that element to the last must be in order. Therefore, rather than simply keeping track of whether a swap occurred in the inner loop or not, if we record where that swap occurred we can reduce the number of inner iterations accordingly. If the position remains zero then we know no swaps occurred and the array must therefore be sorted, therefore we no longer need the swapped variable.

procedure bubblesort (A : list of sortable items)

n := length (A)

repeat

last := 0

for i := 1 to n-1 inclusive do

if A[i-1] > A[i] then

swap (A[i-1], A[i])

last := i

end if

end for

n := last

until n = 0

end procedure

This is as far as we can go with bubble sort. Although these optimisations improve the algorithm complexity by eliminating what would otherwise be redundant comparison operations in the general case, the worst case is still O(n triangular).

As a result of this complexity, the usefulness of bubble sort quickly diminishes the more elements there are. While the same can be said of similar algorithms such as insertion sort, in practice we find that insertion sort performs far better than bubble sort because it doesn't swap any values, it simply copies them. However, although it is a much better algorithm and can work with larger arrays than bubble sort, its usefulness quickly diminishes as well. However, it can be used in divide-and-conquer sorting algorithms like quicksort, which divides and subdivides an array into small unsorted partitions that are themselves in the correct order. When a partition is small enough to be handled by insertion sort, this can improve the quicksort algorithm considerably.

Answer 4

It may be used effectively for sorting small arrays. Its performance is unacceptable in sorting large arrays. It is also the best known, simplest, and easiest to understand.

Answer 5

O(n2)

The complexity of bubble sort is O(n(square))