A bubble sort repeatedly goes through a list, comparing neighbouring values and swapping them if they are out of order.

After each pass through the list, the highest remaining value has “bubbled” through the list to its correct location, so the size of the remaining list to be sorted is reduced by 1.

If no swaps are carried out on a pass, then the sorting can stop.

General Algorithm

DECLARE n INITIALLY length(list)
DECLARE swapped INITIALLY TRUE
 
WHILE swapped AND n >= 0
 
    SET swapped TO False
    FOR i = 0 to n-2 DO
        IF list[i] > list[i+1] THEN
            SET temp TO list[i]
            SET list[i] TO list[i+1]
            SET list[i+1] TO temp
            SET swapped TO TRUE
        END IF
    END FOR 
 
    SET n TO n - 1
END WHILE

listsize = length(list)
swapped = True
 
# as long as previous loop had a swap, and unsorted part of list is not empty
WHILE swapped AND listsize  >= 0:
 
    # new iteration, so reset swaps
    swapped = False
    # go through the unsorted part of the list
    for i in range(listsize-1):
        #if current value is bigger than next value
        if list[i] > list[i+1]:
            #swap the values
            temp = list[i]
            list[i] = list[i+1]
            list[i+1] = temp
            swapped = True
 
    #the unsorted part of the list is now smaller
    listsize -= 1

Swapping List Values

Most languages need the use of a temporary variable to swap two values. This is part of the AH course.

temp = list[i]
list[i] = list[i+1]
list[i+1] = temp

Python can do this in one command:

list[i], list[i+1] = list[i+1], list[i]

In programmer interviews, one task might be to swap two numbers without the use of a temporary variable. This solution works, but requires several calculations:

x = 3
y = 5
 
x = x + y   # x = 3 + 5 = 8
y = x - y   # y = 8 - 5 = 3
x = x - y   # x = 8 - 3 = 5