Bubble Sort

Three implementations are provided:

  • Pseudo code,
  • A basic implemenation of the pseudo code,
  • An enhanced implementation, and
  • A pointer-based implementation.

When compiled with the -O2 option, the basic implementation sorts an array of size 500 thousand in 213 seconds, the enhanced array-based implementation sorts the same list in 79 seconds, and the pointer-based implementation sorts the list in 52 seconds.

Pseudo Code

To bubble sort an array of size n:
	Move through the list
	Continue inserting the next object into the array until
	we create an array of size n.
end

Basic Implementation



Enhanced Implementation on Arrays

This implementation:

  • Avoids unnecessary swaps.


Enhanced Implementation using Pointers

This implementation:

  • Uses pointers to walk through the arrays.