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).
Bubble

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.
Bubble Sort in C Example

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
Bubble sort meme 1

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 program
int main()
{
int array[] = {5, 3, 1, 9, 8, 2, 4,7};
int size = sizeof(array)/sizeof(array[0]);

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 bubbleSort
void 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 program
int main()
{
int array[] = {5, 3, 1, 9, 8, 2, 4,7};
int size = sizeof(array)/sizeof(array[0]);

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 sort
5 3 1 9 8 2 4 7 
After bubble sort:
1 2 3 4 5 7 8 9
Example Bubble Sort in C – 1

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

  • Noob (Bad) algorithm 😀
  • 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.

Time Complexity
For Bubble Search

Best

Ω(n)

Average

Θ(n2)

Worst

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.

Data Structures and Algorithm Learn Sorting