Bubble Sort Pseudocode
To describe our bubble algorithm, we can start with these basic preconditions and postconditions.
- The array stores a type of elements which can be ordered.
- The array will be sorted in ascending order.
We can then represent this algorithm using the following pseudocode.
function BUBBLESORT(ARRAY) (1) # loop through the array multiple times loop INDEX from 0 to size of ARRAY – 1 (2) # consider every pair of elements except the sorted ones loop INDEX2 from 0 to size of ARRAY – 2 – INDEX (3) if ARRAY[INDEX2] > ARRAY[INDEX2 + 1] then (4) # swap elements if they are out of order TEMP = ARRAY[INDEX2] (5) ARRAY[INDEX2] = ARRAY[INDEX2 + 1] (6) ARRAY[INDEX2 + 1] = TEMP (7) end if end loop end loop end function
In this code, we begin by looping through every element in the array, as seen on line 2. 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 3, 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 4 is a comparison between two adjacent elements in the array starting at the index
index2. If they are out of order, we use lines 5 through 7 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
indexelements 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.