Bubble sort is a simple sorting algorithm that sorts the elements in ascending and descending order. It repeatedly compares the adjacent elements and swaps them if they are in the wrong order.

#### Example to understand Bubble Sort,

Suppose there is an array which contains ” 5 1 4 2 8″. If you want to sort this array in ascending order (lowest number to the greatest number), you need to take the following steps,

**First Pass:**

( **5 1** 4 2 8 ) → ( **1 5** 4 2 8 ), Here, the algorithm compares the first two elements and swaps since 5 > 1.

( 1 **5 4** 2 8 ) → ( 1** 4 5** 2 8 ), Swap since 5 > 4

( 1 4 **5 2** 8 ) → ( 1 4 **2 5** 8 ), Swap since 5 > 2

( 1 4 2 **5 8** ) → ( 1 4 2 **5 8** ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

**Second Pass:**

( **1 4** 2 5 8 ) → ( **1 4** 2 5 8 )

( 1 **4 2** 5 8 ) → ( 1 **2 4** 5 8 ), Swap since 4 > 2

( 1 2 **4 5** 8 ) → ( 1 2 **4 5** 8 )

( 1 2 4 **5 8** ) → ( 1 2 4 **5 8** )

**Third Pass:**

( **1 2** 4 5 8 ) → ( **1 2** 4 5 8 )

( 1 **2 4** 5 8 ) → ( 1 **2 4** 5 8 )

( 1 2 **4 5** 8 ) → ( 1 2 **4 5** 8 )

( 1 2 4 **5 8** ) → ( 1 2 4 **5 8** )

#### Below the implementation code,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #include <stdio.h> #define ARRAY_SIZE(x) sizeof(x)/sizeof(x[0]) //Function to swap element void Swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } //Function to sort the array void BubbleSort(int *arr, int n) { int i = 0, j = 0; int swapflag = 0; for (i = 0; i < n-1; i++) { swapflag = 0; for (j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { Swap(&arr[j], &arr[j+1]); swapflag = 1; } } //If inner loop not executed, break the loop if (swapflag == 0) break; } } int main() { int i = 0; //Array int arr[] = {6,5,3,1,8,7,2,4}; //Get array size int n = ARRAY_SIZE(arr); //Function to sort array in ascending order BubbleSort(arr, n); printf("Array in ascending order: \n"); //Print array for (i=0; i < n; i++) { printf("%d ", arr[i]); } return 0; } |

**Output:** Array in ascending order: 1 2 3 4 5 6 7 8

#### Important characteristics of Bubble Sort:

- The best time complexity for Bubble Sort is O(n).
- The average and worst time complexity is O(n²).
- The space complexity for Bubble Sort is O(1).