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.