In this writeup, I assume that the name of the array to be sorted is A,
that it is N entries long, that the entries are indexed 0 to
(N - 1) [inclusive], that element number i of the array is
referenced by A{i}, and that the array is to be sorted so for all
integers i and j between 0 and (N - 1) incusive,
(A{i} ≤ A{j}) iff
(i ≤ j) [i.e. A{0} contains the lowest-valued
element and the values of successive entries in A are nondecreasing].
The basic idea of the bubble sort is to apply the divide and conquer method; reduce the
problem of sorting an entire array to the problem of sorting two adjacent elements, then
apply this simpler problem in a way that will accomplish the larger problem. The problem of
sorting an adjacent pair of elements is very simple; if the element at the lower index has a
greater value then the pair needs to be swapped, otherwise the pair are already sorted
[relative to each other, at least - not necessarily sorted in the larger context of
the entire array]. A 'pass' is made through the array, sorting the pair
A{0} and A{1}, then the pair A{1} and A{2}, and
every pair, in order, up to A{N - 2} and
A{N - 1} [thus, a pass consists of (N - 1)
adjacent-pair-sorts]. It can be proved that after each pass, at least one more element
is guaranteed to be in the correct position, so at most (N - 1) passes are
necessary to sort the entire array [if (N - 1) elements are properly sorted,
there's no place for the Nth element to be but it's
properly sorted place too]. A simplistic implementation of the bubble sort looks
like this:
i := 0
while (
i < (
N - 1))
j := 0
while (
j < (
N - 1))
if (
A{
j} >
A{
j + 1})
swap
A{
j} and
A{
j + 1}
end if
j := (
j + 1)
end while
i := (
i + 1)
end while
This takes (N - 1)2 adjacent-pair-sorts. By
realising that after one sweep, the greatest element must be at the highest index and
generalising from there, one can see that the highest elements can be ignored
on later passes so new, better code can be written:
i := (
N - 1)
while (
i > 0)
j := 0
while (
j <
i)
if (
A{
j} >
A{
j + 1})
swap
A{
j} and
A{
j + 1}
end if
j := (
j + 1)
end while
i := (
i - 1)
end while
This takes ((N - 1) * (N - 2) / 2) adjacent-pair-sorts, less than
half the number of the first code. Another optimisation can be added: if, on any pass,
there are no swaps, this means that the array is sorted, and the sort algorithm can end.
This adds a little more processing to each pass, but the beneft of saving a few passes can
so outweigh the cost of the little extra processing in each pass that it is generally
considered a good idea to include it.
i := (
N - 1)
DidSwap := true
while ((
i > 0) ∧ (
DidSwap = true))
DidSwap := false
j := 0
while (
j <
i)
if (
A{
j} >
A{
j + 1})
swap
A{
j} and
A{
j + 1}
DidSwap := true
end if
j := (
j + 1)
end while
i := (
i - 1)
end while
Finally, when one considers a mostly-sorted array [e.g. an array that is fully
sorted, but has an extra element added onto the end with a value lower than any other
entry], another optimisation comes to mind. A pass through the array from the lowest
index to the highest ensures that the greatest element is properly sorted. Likewise, a pass
from the highest index to the lowest would ensure the least element is properly sorted. A
sweeping back-and-forth of passes would therefore most likely perform better on a
mostly-sorted array.
limit{-1} := -1
limit{1} := (
N - 1)
i := 0
direction := 1
DidSwap := true
while (((
limit{-1} + 1) <
limit{1}) ∧ (
DidSwap = true))
DidSwap := false
while (
i ≠
limit{
direction})
if (
A{
i} >
A{
i + 1})
swap
A{
i} and
A{
i + 1}
DidSwap := true
end if
i := (
i +
direction)
end while
limit{
direction} := (
limit{
direction} -
direction)
i := (
limit{
direction} -
direction)
direction := -
direction
end while
All array entries with index lower than or equal to limit{-1} are sorted, and
all array entries with index higher than limit{1} are sorted, at all times.
direction is 1 for an ascending sweep through the array, and is -1 for a
descending sweep. Once a pass is completed, the appropriate limit has
direction subtracted from it, so the next pass in the same direction won't go
unnecessarily far into a part of the array which is known to be sorted already.
i is reinitialised to start the sweep in the opposite direction, so that it
doesn't start in the part of the array which is known to be sorted already, and
direction is inverted so the next sweep is in the opposite direction.