# Bubble sort

## Contents

# 14.3. Bubble sort#

Bubble Sort is a simple sorting algorithm that works by repeatedly stepping through the list, comparing each pair of adjacent elements and swapping them if they are in the wrong order. The process is repeated until the entire list is sorted. The algorithm gets its name because the smaller elements “bubble” to the top of the list, while the larger elements “sink” to the bottom.

## 14.3.1. Algorithm#

Bubble sort works as follows:

In the first iteration, compare the first element with the second element. If the first element is greater than the second element, swap them. Otherwise, do nothing. Then, compare the second element with the third element. If the second element is greater than the third element, swap them. Otherwise, do nothing. The process repeats till the last element of the array. After the first iteration, the last element of the array is sorted, and is holding the maximum element of the array. We “bubbled” the last element to the end of the array.

In the second iteration, compare the first element with the second element. If the first element is greater than the second element, swap them. Otherwise, do nothing. Then, compare the second element with the third element. If the second element is greater than the third element, swap them. Otherwise, do nothing. The process repeats till the

**second**last element of the array. After the second iteration, the last two elements of the array are sorted, holding the maximum two elements of the array.In the third iteration, compare the first element with the second element. If the first element is greater than the second element, swap them. Otherwise, do nothing. The process repeats till the

**third**last element of the array. After the third iteration, the last three elements of the array are sorted, holding the maximum three elements of the array. In our example, this is the last iteration because the array has only four elements. Hence, the maximum number of iterations is the size of the array minus one.

**Save iterations.** To save iterations, we can stop the algorithm if the array is already sorted at any point in time. We can do this by keeping track of whether a swap has occurred in the current iteration. If no swap has occurred, we can stop the algorithm.

## 14.3.2. Pseudocode#

We write pseudocode for bubble sort as follows:

Set

`top`

to`n - 1`

, where`n`

is the size of the array.Set index

`ind`

to`0`

.Set

`sorted`

to`false`

.Compare the element at index

`ind`

with the element at index`ind + 1`

. If the element at index`ind`

is greater than the element at index`ind + 1`

, swap them. If we swap, this means the array wasn’t sorted and their were two elements out of order, so we set`sorted`

to`false`

. Otherwise, do nothing.Increment

`ind`

by`1`

.Repeat steps \(4\) and \(5\) until

`ind`

is equal to`top`

.If

`sorted`

is`true`

, stop the algorithm. Otherwise, set`top`

to`top - 1`

and go to step \(2\).

## 14.3.3. Implementation#

We implement bubbble sort as follows. In lines \(1\) to \(5\), we implement the swap function that swaps two `int`

values. We implemented the swap function before in Section 6.3. Download `bubble-sort.c`

if you want to play with the code.

**Code**

```
1void swap(int *x, int *y) {
2 int temp = *x;
3 *x = *y;
4 *y = temp;
5}
6
7void printArray(int list[], int n) {
8 for (int i = 0; i < n; i++) {
9 printf("%d ", list[i]);
10 }
11 printf("\n");
12}
13
14void bubbleSort(int list[], int n) {
15 bool sorted = false;
16
17 for (int top = n - 1; top > 0 && !sorted; top--) {
18 sorted = true;
19 for (int i = 0; i < top; i++) {
20 if (list[i] > list[i + 1]) {
21 swap(&list[i], &list[i + 1]);
22 sorted = false;
23 }
24 }
25 printf("After iteration %d: ", n - top);
26 printArray(list, n);
27 }
28}
29
30int main(void) {
31 int list[4] = {2, 5, 3, 1};
32
33 bubbleSort(list, 4);
34 printArray(list, 4);
35 return 0;
36}
```

**Output**

After iteration 1: 2 3 1 5 After iteration 2: 2 1 3 5 After iteration 3: 1 2 3 5 1 2 3 5