What are the characteristics of the bubble sort algorithm?

Answer 1

Bubble sort is a stable, in-place sort with a best, worst and average case of O(n!) for n elements, thus making it highly inefficient and entirely unsuitable for sorting large amounts of data. For this reason bubblesort is often cited as an example of how not to write an algorithm.

The algorithm starts by accepting a zero-based array with n elements (0 to n-1). While n is greater than 1, the algorithm iterates an outer loop. On each iteration of the outer loop, an inner loop traverses from element index 1 to n-1. On each iteration of the inner loop, the element at the current index is compared with the element at the previous index. If they are out of order, the two elements are swapped. When the inner loop has finished, n is decremented. At this point element n is now its correct place and is ignored on the next iteration of the outer loop. When n is not greater than 1, all the elements are sorted and the outer loop terminates.

In other words, the algorithm locates the largest value in the range 0 to n-1 and places it at index n-1 (bubbling it up the list with each swap). After decrementing n, everything from element n up is sorted and everything below n is unsorted, thus creating two subarrays split at n. On each pass, the sorted subarray gains a new element and the unsorted subarray loses an element. When there is only one element in the unsorted subarray, the entire array is sorted.

The inefficiency of the algorithm is that it takes no account of elements at the end of the unsorted subarray that may already be in their correct position. The algorithm can be improved with the observation that the position of the last swap at the end of the inner loop means that everything from that point forwards is already sorted and don't need to be compared on the next pass. So rather than reducing the unsorted subarray by just one element, the subarray can be reduce by one or more elements. To achieve this we initialise a temporary variable with the value zero at the start of the outer loop, and whenever a swap occurs in the inner loop we assign the current index to the temporary variable. When the inner loop ends, the temporary variable indicates where the last swap occured and we can assign that value to n, which may reduce n by one or more elements on each pass. The only other change we need to make is that the outer loop now terminates when n is zero (the initial value of the temporary variable), which means no swaps occured on the last iteration of the inner loop, so everything must be sorted.

Even with this optimisation the worst case is still O(n!) if the list is completely reversed. However, for an already-sorted list the best case becomes O(n). Since these two extremes are isolated cases, the average case is somewhere in between, around O(n!/2), which is still highly inefficient and unsuitable for large amounts of data.

The following is an implemention of an optimal bubble sort in C++:

template<typename _Ty>

void bubble (std::vector<_Ty>& A)

{

unsigned size = A.size();

while (size)

{

unsigned temp = 0; // records last swap position

for (unsigned index=1; index<size; ++index)

{

if (A[index]<A[index-1])

{

std::swap (A[index],A[index-1]);

temp=index;

}

}

size = temp;

}

}

Answer 2

Bubble sort is a highly inefficient sorting algorithm, often cited as an example of how not to write an algorithm. Bubble sort is trivial to implement but has O(n*n) complexity when sorting n items. While perfectly adequate for small data sets, it is wholly inappropriate for large sets. Nevertheless, insert sort is, on average, more efficient for sorting small sets.