# Bubble Sort in C

## Bubble Sort in C

Sorting is the process of arranging the data in some logical order.  Bubble sort is an algorithm to sort various linear data structure.

The logical order can be ascending and descending in case of numeric values or dictionary order in case of alphanumeric values.

•  Bubble Sort is very simple and easy  to implement sorting  technique.
• In bubble sort technique,each pair of element is compared.
• Element are swapped if they are not in order.
• The worst case complexity of bubble sort is O(n2). ### Implementation of Bubble Sort

Let’s take an example ,we have a list of number stored in array

• Logic start with comparison of first two element and if the left element is greater than right element,they swap their position. comparison continue till the end of array.
• If we talk about the example taken in the below image, the first will be in between 28 and 6.
• Since the left element i.e; 6 is smaller than the right element i.i; 28, they will get swapped.
• Similarly, in the next iteration we will compare 28 and 4, and again they will get swapped.
• This, process will continue until the loop reaches the  end of the array, this will be regarded as Pass 1, at the end of which we have the largest element on the right most end.
• Passes like this will continue until we have all the elements in their correct order, you can refer to the image below, for better understanding. ### Algorithm of Bubble Sort

• Step 1: Repeat for round=1,2,3…..N-1
• Step 2: Repeat For i=0,1,2…N-1 round
• Step 3: IF A[i] > A[i+1]

SWAP A[i] and A[i+1]

[END OF INNER LOOP]

[END OF OUTER LOOP

• Step 4: Return ### Code of Bubble Sort

`#include <stdio.h>/* Function to print array */void display(int arr[], int size) {     int i;     for (i=0; i < size; i++)         printf("%d ", arr[i]);     printf("\n"); } // Main function to run the programint main() {     int array[] = {5, 3, 1, 9, 8, 2, 4,7};     int size = sizeof(array)/sizeof(array);     printf("Before bubble sort: \n");    display(array, size);       int i, j, temp;    for (i = 0; i < size-1; i++){              // Since, after each iteration righmost i elements are sorted          for (j = 0; j < size-i-1; j++)             if (array[j] > array[j+1])            {              temp = array[j]; // swap the element              array[j] = array[j+1];               array[j+1] = temp;            }    }    printf("After bubble sort: \n");     display(array, size);     return 0; } `
`#include <stdio.h>void swap(int *var1, int *var2) {     int temp = *var1;     *var1 = *var2;     *var2 = temp; } // Here we are implementing bubbleSortvoid bubbleSort(int arr[], int n) {    int i, j;    for (i = 0; i < n-1; i++)              // Since, after each iteration righmost i elements are sorted          for (j = 0; j < n-i-1; j++)             if (arr[j] > arr[j+1])               swap(&arr[j], &arr[j+1]); } /* Function to print array */void display(int arr[], int size) {     int i;     for (i=0; i < size; i++)         printf("%d ", arr[i]);     printf("\n"); } // Main function to run the programint main() {     int array[] = {5, 3, 1, 9, 8, 2, 4,7};     int size = sizeof(array)/sizeof(array);     printf("Before bubble sort: \n");    display(array, size);     bubbleSort(array, size);    printf("After bubble sort: \n");     display(array, size);     return 0; } `

#### Output

After Sorted Element List

`Before bubble sort5 3 1 9 8 2 4 7 After bubble sort:1 2 3 4 5 7 8 9` ## Performance Based Analysis of Bubble Sort Algorithm

### Pros

• Easy to implement
• Cool to implement
• Gives the largest value of array in the first iteration itself.
• Or the smallest value of array in the first iteration itself (Minor tweak in implementation)
• No demand for large amounts of memory for operation

### Cons

• Very horrible time complexity of O(n2)

### Interesting Facts

1. Average and worst case time complexity: o(n2)
2. Best case time complexity: n when array is already sorted.
3. Worst case: when the array is reverse sorted. Ω(n)

Θ(n2)

O(n2)

## Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews. 