Bubble Sort Pseudocode

To describe our bubble algorithm, we can start with these basic preconditions and postconditions.

Preconditions:

The array stores a type of elements which can be ordered.

Postconditions:

The array will be sorted in ascending order.

We can then represent this algorithm using the following pseudocode.

 1function BUBBLESORT(ARRAY)
 2    # loop through the array multiple times
 3    loop INDEX from 0 to size of ARRAY – 1
 4        # consider every pair of elements except the sorted ones
 5        loop INDEX2 from 0 to size of ARRAY – 2 – INDEX
 6            if ARRAY[INDEX2] > ARRAY[INDEX2 + 1] then
 7                # swap elements if they are out of order
 8                TEMP = ARRAY[INDEX2]
 9                ARRAY[INDEX2] = ARRAY[INDEX2 + 1]
10                ARRAY[INDEX2 + 1] = TEMP
11            end if
12        end loop
13    end loop
14end function

In this code, we begin by looping through every element in the array, as seen on line 3. Each time we run this outer loop, we’ll lock one additional element in place at the end of the array. Therefore, we need to run it once for each element in the array.

On line 5, we’ll start at the beginning of the array and loop to the place where the sorted portion of the array begins. We know that after each iteration of the outer loop, the value index will represent the number of locked elements at the end of the array. We can subtract that value from the end of the array to find where we want to stop.

Line 6 is a comparison between two adjacent elements in the array starting at the index index2. If they are out of order, we use lines 8 through 10 to swap them. That’s really all it takes to do a bubble sort!

Looking at this code, we can describe the invariant of our outer loop as follows:

The last index elements in the array are in sorted order, and
The elements in the array have not changed, only their positions.

Notice how this differs from selection sort, since it places the sorted elements at the beginning of the array instead of the end. However, the result is the same, and by the end of the program we can show that each algorithm has fully sorted the array.