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 `N`^{th} 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.