# Bubble Sort 1

In Brief | This sorting algorithm performs multiple passes over a list, comparing consecutive elements. If the two elements are out of order, they are swapped. This continues until a pass shows all elements in order.... more |

` 1 function bubble_sort(array)`

2

3 do

4 swapped = False

5

6 for i = 0 → len(array) - 2

7 if array[i] > array[i + 1]

8 swap(array[i], array[i+1]) // Swap the element positions

9 swapped = True

10

11 while swapped == True

12

13 return array

This sorting algorithm performs multiple passes over a list, comparing consecutive elements. If the two elements are out of order, they are swapped. This continues until a pass shows all elements in order.

It is named 'bubble sort' because smaller elements slowly 'bubble up' towards the top of the list.

This is one of easiest sorting algorithms to implement but also one of the slowest.

## An Example

Say I have the following list I wish to sort:

[2 4 1 3]

The algorithm makes multiple passes over the list, comparing adjacent elements. Each pass will compare adjacent numbers, and if the left one is larger than the right one it will swap them. Below, bold indicates the numbers being examined.

Watch how the smaller numbers gradually bubble up.

### The First Pass

[**2 4** 1 3] The first two numbers are in order, so nothing happens.

[2 **4 1** 3] → [2 **1 4** 3] The next pair is not in order, and so is flipped.

[2 1 **4 3**] → [2 1 **3 4**] Again, the two numbers are not in order. They are swapped.

### The Second Pass

[**2 1** 3 4] → [**1 2** 3 4]

[1 **2 3** 4] (no change)

[1 2 **3 4**] (no change)

### The Third Pass

[**1 2** 3 4] (no change)

[1 **2 3** 4] (no change)

[1 2 **3 4**] (no change)

Since nothing was changed on this pass, the list must be in order and the sort terminates.