• 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 2024
  • 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
    • IDE
    • CV Builder
    • Other Tools …
  • Jobs

Bubble Sort in C Program | Example | Algorithm | Complexity

Aniruddha Chaudhari/36036/2
C / C++CodeData Structure

Table of Contents

  • What is the Bubble Sort?
  • Bubble Sort Algorithm [Step by step]
  • How does Bubble Sort Work?
  • C Program to Implement Bubble Sort
  • Bubble Sort Time Complexity
  • Advantages of Bubble Sort
  • Disadvantages of Bubble Sort

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 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 to 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 elements 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, 30, 12, 92, 47};
  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: 34 30 12 92 47 
Sorted array: 12 30 34 47 92

Bubble Sort Time 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 for swapping elements 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 questions, 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- Array
  7. C- Function (Types/Call)
  8. C- strlen() vs sizeof()
  9. C- Nested Switch Statement
  10. C- Recursion
  11. C- Dynamic Programming
  12. C- Storage Classes
  13. C- Creating Header File
  14. C- Null Pointer
  15. C- Stack and Queue
  16. C- Implement Stack using Array
  17. C- Implement Linked List in C
  18. C- File Handling
  19. 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

© 2022 – 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