• Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard
CSEstack

What do you want to Learn Today?

  • Programming
    • Tutorial- C/C++
    • Tutorial- Django
    • Tutorial- Git
    • Tutorial- HTML & CSS
    • Tutorial- Java
    • Tutorial- MySQL
    • Tutorial- Python
    • Competitive Coding Challenges
  • CSE Subject
    • (CD) Compiler Design
    • (CN) Computer Network
    • (COA) Computer Organization & Architecture
    • (DBMS) Database Management System
    • (DS) Data Structure
    • (OS) Operating System
    • (ToA) Theory of Automata
    • (WT) Web Technology
  • Interview Questions
    • Interview Questions- Company Wise
    • Interview Questions- Coding Round
    • Interview Questions- Python
    • Interview Questions- REST API
    • Interview Questions- Web Scraping
    • Interview Questions- HR Round
    • Aptitude Preparation Guide
  • GATE 2021
  • Linux
  • Trend
    • Full Stack Development
    • Artificial Intelligence (AI)
    • BigData
    • Cloud Computing
    • Machine Learning (ML)
  • Write for Us
    • Submit Article
    • Submit Source Code or Program
    • Share Your Interview Experience
  • Tools

Complete Bubble Sort in C with Explanation | Algorithm, Program and Complexity

Aniruddha Chaudhari/29046/2
C / C++CodeData Structure
YouTube CSEstack

Table of Content:

  • What is the Bubble Sort?
  • Bubble Sort Algorithm
  • How does Bubble Sort Work?
  • C Program to Implement Bubble Sort
  • Bubble Sort Complexity
  • Advantages
  • Disadvantages

 

What is the Bubble Sort?

It is the basic sorting algorithm to sort array elements. It compares the pair of adjacent elements from an array. If the order is wrong, it just swaps the element.

If there are n-elements in the array, it iterates loop n times. In each iteration, one element is placed in the order at the end of the array.

It is not easy to understand this algorithm with words. So, in this post, I will ponder Bubble sort in C with the explanation in detail. It will make your understanding clear.

Bubble Sort Algorithm [Step by step]

Here is an algorithm for Bubble Sort.

  • Take the array as input
  • For each element (say x) in the array
    • For each adjacent element (say y) to x in the array
      • Compare element x with y.
      • Swap if it is not in order

How does Bubble Sort Work?

Let’s take an array of elements 52, 35, 91, 31, 56

Here we want to order it in the ascending order.

Iteration 1:

Keep a pointer to the first element (5) and compare it with 35. As 35 is lower than 52, swap it.

Result array: 35, 52, 91, 31, 56

Increment the pointer to point the second element i.e. 52. Compare it with the 3rd element (91). As 91 is greater than 52, do nothing.

Increment the pointer to point 3rd element (91) compare with the 4th element (31). As 91 is greater than 31, just swap them.

Result array: 35, 52, 31, 91, 56

Again increment the pointer and compare 91 with 56. As 91 is greater than 56, swap them.

Result array: 35, 52, 31, 56, 91

You can see, the largest element has reached the last position.

Bubble Sort in C with Explanation

Iteration 2:

After the second iteration,

Result array: 35, 31, 52, 56, 91

The array is partitioned into two parts; the second half is sorted (mentioned above in bold format).

Note: To optimize the algorithm, you can skip comparing element with the elements from the second half.

Iteration 3:

Result array: 35, 31, 52, 56, 91

Iterate the above steps (n-1) times (until you get a sorted array).

Iteration 4:

Final sorted array: 31, 35, 52, 56, 91

C Program to Implement Bubble Sort

Here is a complete code for bubble sort.

#include<stdio.h>

void main()
{
  int nArr[]={34, 35, 91, 92, 93};
  int nSize = sizeof(nArr)/sizeof(int);
  int i=0, j=0, t=0;

  //Special Case to reduce complexity in Best Case(O(n))
  int nSorted= 0;		

  printf("\nInput  array: ");
  for(i=0;i<nSize;i++)
  { 
    printf("%d ", nArr[i]); 
  }

  for(i = nSize-1; i>0 && nSorted == 0; i--)
  {
    nSorted = 1;
    for(j=0;j<i;j++) { if(nArr[j]>nArr[j+1])
      {
        t= nArr[j];
        nArr[j]=nArr[j+1];
        nArr[j+1] = t;			
        nSorted = 0;
      }
    }
  }

  printf("\nSorted array: ");
  for(i=0;i<nSize;i++)
    printf("%d ", nArr[i]);
}

The output of a program:

Input array: 52, 35, 91, 31, 56
Sorted array: 31, 35, 52, 56, 91

Bubble Sort Complexity:

Loops run twice for each element in an array so it takes time O(n^2). 

Let’s take the best case where the input array is already sorted. There is no need of swapping element and only one iteration is required. So the best case complexity is  Ω(n).

In average and worst cases, it compares each element to its adjacent element in the array. It requires n iterations. So the average case and worst case complexity are O(n^2).

Worst Case Complexity: O(n^2)

Best Case Complexity: Ω(n)

Average Case Complexity: O(n^2)

Advantages of Bubble Sort:

What are the advantages of using Bubble sort?

  • The bubble sort algorithm is easy to understand and to implement. Complete code work on two loops. You just have to figure out how does these two loops actually work.
  • It does not require any extra space as it is an in-place sorting algorithm.
  • It takes on Ω(n) time in the best case.

Disadvantages of Bubble Sort:

What are the disadvantages of using Bubble sort?

  • It has a time complexity of O(n^2) in average and worst cases.
  • There are so many alternative algorithms which take O(n*log(n)) time for sorting. So bubble sort is slower than most of sorting algorithms.

Other Sorting Algorithm:

  • Selection Sort in C with Explanation (Algorithm, Program & Time Complexity)
  • Quick Sort in C with Explanation (Algorithm, Program & Time Complexity)

This is all about bubble sort in C with explanation. If you have any question, please write in a comment.

bubble sortsorting
Aniruddha Chaudhari
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on CSEstack.org portal.

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Comments

  • Reply
    Jacob Vetter
    November 13, 2019 at 6:59 pm

    Hello, I to am Python nut. I very much appreciate as you share your coding knowledge. Keep up.

    • Reply
      Aniruddha Chaudhari
      November 13, 2019 at 10:11 pm

      You motivate me to learn and share more with you. Thanks, Jacob!

Leave a Reply Cancel reply

C Programming

  1. C- Introduction
  2. C- Compile & Execute Program
  3. C- Data Types
  4. C- if-else statement
  5. C- While, do-while, for loop
  6. C- Function (Types/Call)
  7. C- strlen() vs sizeof()
  8. C- Nested Switch Statement
  9. C- Recursion
  10. C- Dynamic Programming
  11. C- Storage Classes
  12. C- Creating Header File
  13. C- Null Pointer
  14. C- Stack and Queue
  15. C- Implement Stack using Array
  16. C- Implement Linked List in C
  17. C- File Handling
  18. C- Makefile Tutorial

Object Oriented Concepts in C++

  • C++: C vs OOPs Language
  • C++: Introduction to OOPs Concepts
  • C++: Inheritance

Sorting Algorithms

  • Different Types of Sorting Algo
  • Selection Sort
  • Bubble Sort
  • Quick Sort

Programming for Practice

  1. Online C/C++ Compiler

String Handling:

  1. Remove White Spaces from String
  2. Implement strstr Function in C
  3. Convert String to Int – atoi()
  4. Check if String is Palindrome
  5. Check if Two Strings are Anagram
  6. Split String in using strtok_r()
  7. Undefined reference to strrev

Array:

  1. Check if Array is Sorted

Bit Manipulation:

  1. Count Number of 1’s in Binary

Linked List:

  1. Reverse a Linked List Elements

Number System:

  1. Program to Find 2’s Complement
  2. Convert Decimal to Binary in C

Tricky Questions:

  1. Add Two Numbers without Operator
  2. Find Next Greater Number
  3. Swap values without temp variable
  4. Print 1 to 100 without Loop

Interview Coding Questions

  • 50+ Interview Coding Questions

© 2021 – CSEstack.org. All Rights Reserved.

  • Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard