What is a Bubble Sort?
Bubble Sort is a simple sorting algorithm commonly used to sort elements in a list or array. It works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. The algorithm iterates through the list multiple times until no more swaps are needed, resulting in a sorted sequence. During each iteration, the largest unsorted element "bubbles" up to its correct position, hence the name "Bubble Sort."
In this article, you will learn about bubble sort and how to write a C program for bubble sort implementation using different ways.
Watch the video below that will help you understand what is bubble sort algorithm and how bubble sort works in real-time.
How Does Bubble Sort Work?
Bubble sort is a data sorting algorithm that works by randomly copying elements from the first array into a smaller second array, and then reversing the order of these arrays. After this process has been repeated multiple times, the sorted data will be located in the middle of the larger array.
The basic idea behind the bubble sort is to compare the elements of an array one by one until they are sorted in ascending order, which is called bubble bursting. When an element needs to be moved, instead of moving the entire array, only the element affected by the change is moved. This technique conserves memory and keeps overall execution speed high because there are fewer updates than with other sorting algorithms.
1. First Iteration (Compare and Swap)
Bubble Sort is a sorting algorithm that works by first sorting the items into two piles, and then swapping the items in each pile until they are sorted in reverse order. This process is known as the First Iteration of Bubble Sort.
For example, we need to sort these elements -5, 72,0, 33, - 9, then the sequence will work in this way.
- Starting with the first index, the first and second components should be juxtaposed.
- The first and second elements are switched if the first one is bigger.
- Compare the second and third items right now. If they are not in the proper sequence, swap them.
- The method described above continues until the last component.
Bubble sort first iteration in C program
#include<stdio.h>
int main() {
double Array[5]; // array to be sorted
double temp; // temporary variable to hold the current element of the array
void bubbleSort(Array); // function that performs bubble sort on a given array
while (true) {
temp=Array[0]; /* swap two elements */
Arrays[1]=Arrays[2]; /* update second position */
Arrows ++; /* make next move */
}/*endwhile*/ // loop body }// end of Bubble Sort First Iteration in C programming language2. Remaining Iteration
The Bubble Sort is an efficient sorting algorithm that works in O(n log n) time, where n is the number of items to be sorted. The first iteration of the Bubble Sort sorts the input item at index 0 into ascending order, and then repeats this process until all the inputs have been sorted. So, after performing one iteration of the bubble sort on an input dataset containing five items, there would be four remaining iterations left to perform.
Implementation of Bubble Sort in C
To implement Bubble Sort in C, we start by defining a function that takes an array and its size as parameters. Inside the function, we use nested loops to iterate through the array. The outer loop runs for the total number of elements in the array, while the inner loop compares adjacent elements and swaps them if they are in the wrong order.
This process continues until the end of the array is reached. We also need a flag variable to track whether any swaps occurred during each pass. If no swaps are made in a pass, it means the array is already sorted, and we can terminate the loop early. Once the sorting is complete, the array will be in ascending order.
The Bubble Sort Algorithm in C
The basic bubble sort algorithm can be explained as follows:
bubbleSort(array)
for i <- 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap leftElement and rightElement
end bubbleSort
This algorithm does the swapping of elements to get the final output in the desired order. For instance, if you pass an array consisting of the elements: (6, 3, 8, 2, 5, 7), the final array after the bubble sort implementation will be: (2, 3, 5, 6, 7, 8).
Read more: Array in C
How Does the C Program for Bubble Sort Work?
As mentioned, the C program for bubble sort works by comparing and swapping adjacent elements in an array. Let’s understand this in a step-by-step method:
Suppose we want to sort an array, let’s name it arr, with n elements in ascending order; this is how the bubble sort algorithm will work.
- Starts from the first index: arr[0] and compares the first and second element: arr[0] and arr[1]
- If arr[0] is greater than arr[1], they are swapped
- Similarly, if arr[1] is greater than arr[2], they are swapped
- The above process continues until the last element arr[n-1]
All four steps are repeated for each iteration. Upon completing each iteration, the largest unsorted element is moved to the end of the array. Finally, the program ends when no elements require swapping, giving us the array in ascending order. Now that we know the working of the bubble sort let’s implement it in C programming using different methods.
Optimized Bubble Sort Algorithm
An optimized bubble sort algorithm is one that performs better than the standard bubble sort algorithm. The main benefit of an optimized bubble sort algorithm is that it takes less time to execute, which can be important in applications where performance is a critical factor.
How to optimize the bubble sort?
- We may add a new variable, which is called swap, that has been switched into the optimized bubble sort to optimize the bubble sort. The value of swap is set to be true if there is an element swap. If not, it is set to be false.
- If no swapping occurs after an iteration, the value of swapping will be false. This indicates that the elements have already been sorted and that no more iterations are required.
- This will speed up the process and optimize bubble sort efficiency.
Algorithm for Optimized Bubble Sort
bubbleSort(array)
swapped <- false
for i <- 1 to index Of Last Unsorted Element-1
if left Element > right Element
swap left Element and right Element
swapped <- true
end bubbleSort
The Complexity of Bubble Sort in C
Time Complexity
- Worst Case Complexity: If the array elements are in descending order and we want to make it in ascending order, it is the worst case. The time complexity for the worst case is O(n²).
- Best Case Complexity: The best case is when all the elements are already sorted, and no swapping is required. The time complexity in this scenario is O(n).
- Average Case Complexity: This is the case when the elements are jumbled. The time complexity for the average case in bubble sort is O(n²).
Space Complexity
- Space complexity for the standard bubble sort algorithm is O(1) as there is one additional variable required to hold the swapped elements temporarily.
- Space complexity for optimized implementation of the bubble sort algorithm is O(2). This is because two additional variables are required.
Advantages and Disadvantages of Bubble Sort
Advantages of Bubble Sort
- Simplicity: Easy to understand and implement.
- Minimal code: Requires minimal lines of code for implementation.
- Suitable for small datasets: Works well for small-sized arrays or lists.
- Stable: Elements with equal values retain their relative order.
Disadvantages of Bubble Sort
- Inefficiency: Time complexity of O(n^2) makes it inefficient for large datasets.
- Slow for large arrays: Takes more time to sort compared to more efficient algorithms.
- Not suitable for real-world applications: Other sorting algorithms like Quick Sort or Merge Sort are preferred for practical use.
- Lacks scalability: Does not perform well when dealing with a vast number of elements.
Bubble Sort Applications
The best scenarios to use the bubble sort program in C is when:
- Complexity does not matter
- Slow execution speed does not matter
- Short and easy to understand coding is preferred
Alternatives to Bubble Sort in C
Besides the bubble sort algorithm, you can also sort arrays and lists using the following sorting algorithms.
- Quicksort
- Selection sort
- Merge sort
- Insertion sort
C Program for Bubble Sort Using for Loop
We will write the first C program for bubble sort using a for loop. In this example, we will a use nested for loop in C to sort the elements of a one-dimensional array. To begin with, we will ask for the total number of elements and then the values from the user. Once we get the elements, we will use the for loop to iterate through the elements and sort them in ascending order.
#include <stdio.h>
int main(){
int arr[50], num, x, y, temp;
printf("Please Enter the Number of Elements you want in the array: ");
scanf("%d", &num);
printf("Please Enter the Value of Elements: ");
for(x = 0; x < num; x++)
scanf("%d", &arr[x]);
for(x = 0; x < num - 1; x++){
for(y = 0; y < num - x - 1; y++){
if(arr[y] > arr[y + 1]){
temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
}
printf("Array after implementing bubble sort: ");
for(x = 0; x < num; x++){
printf("%d ", arr[x]);
}
return 0;
}
Output:
C Program for Bubble Sort Using While Loop
For this example, we will follow the same method as in the previous example. The only difference is that we will replace the for loop with the nested while loop.
#include <stdio.h>
int main(){
int arr[50], num, x, y, temp;
printf("Please Enter the Number of Elements you want in the array: ");
scanf("%d", &num);
printf("Please Enter the Value of Elements: ");
for(x = 0; x < num; x++)
scanf("%d", &arr[x]);
x = 0;
while(x < num - 1){
y = 0;
while(y < num - x - 1){
if(arr[y] > arr[y + 1]){
temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
y++;
}
x++;
}
printf("Array after implementing bubble sort: ");
for(x = 0; x < num; x++)
printf("%d ", arr[x]);
return 0;
}Output:
C Program for Bubble Sort Using Functions
In this C program for bubble sort, we will create a user-defined function and write down the mechanism of sorting the array elements inside it. Here’s how to implement bubble sort in C using functions.
#include <stdio.h>
void bubbleSortExample(int arr[], int num){
int x, y, temp;
for(x = 0; x < num - 1; x++){
for(y = 0; y < num - x - 1; y++){
if(arr[y] > arr[y + 1]){
temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
}
}
int main(){
int arr[50], n, x;
printf("Please Enter the Number of Elements you want in the array: ");
scanf("%d", &n);
printf("Please Enter the Value of Elements: ");
for(x = 0; x < n; x++)
scanf("%d", &arr[x]);
bubbleSortExample(arr, n);
printf("Array after implementing bubble sort: ");
for(x = 0; x < n; x++){
printf("%d ", arr[x]);
}
return 0;
}
Output:
C Program for Bubble Sort Using Pointers
In this C program for bubble sort, we have used C pointers. All we did was create another user-defined function to standardize the use of pointers in it. Here’s how the implementation goes.
#include <stdio.h>
void SwapFunc(int *i, int *j){
int Temp;
Temp = *i;
*i = *j;
*j = Temp;
}
void bubbleSortExample(int arr[], int num){
int x, y, temp;
for(x = 0; x < num - 1; x++) {
for(y = 0; y < num - x - 1; y++) {
if(arr[y] > arr[y + 1]) {
SwapFunc(&arr[y], &arr[y + 1]);
}
}
}
}
int main(){
int arr[50], n, x;
printf("Please Enter the Number of Elements you want in the array: ");
scanf("%d", &n);
printf("Please Enter the Value of Elements: ");
for(x = 0; x < n; x++)
scanf("%d", &arr[x]);
bubbleSortExample(arr, n);
printf("Array after implementing bubble sort: ");
for(x = 0; x < n; x++)
{
printf("%d ", arr[x]);
}
return 0;
}
Output:
C Program for Optimized Implementation of Bubble Sort
All the elements are compared in standard bubble sorting even if the last elements are already sorted based on the previous iterations. This increases the execution time, which can be reduced by optimizing the C program for bubble sort. All we need to do is introduce an additional variable; let’s name it Swap.
The variable Swap is set as true if the swapping of elements has occurred; otherwise, it is false. When the program finds that the value of the Swap variable is false, it will understand that the sorting is already done and break out of the loop. This will reduce the execution time by optimizing the algorithm. The code below shows how to optimize the C program for bubble sort.
#include <stdio.h>
// Function for bubble sorting
void bubbleSortExample(int arr[], int n){
for (int i = 0; i < n - 1; ++i){
int Swap = 0;
// Comparing array elements
for (int x = 0; x < n - i - 1; ++x){
if (arr[x] > arr[x + 1]){
int temp = arr[x];
arr[x] = arr[x + 1];
arr[x + 1] = temp;
Swap = 1;
}
}
if (Swap == 0){ // No swapping required
break;
}
}
}
void displayArray(int arr[], int n){
for (int x = 0; x < n; ++x){
printf("%d ", arr[x]);
}
printf("\n");
}
// Driver method
int main(){
int data[] = {27, 13, -54, 93, -20};
// finding array's length
int n = sizeof(data) / sizeof(data[0]);
bubbleSortExample(data, n);
printf("Array after implementing bubble sort: \n");
displayArray(data, n);
}
Output:
Bubble Sort Code in Python, Java, and C/C++
Bubble Sort Code in Python
def bubbleSort(array):
# loop to access each array element
for i in range(len(array)):
# loop to compare array elements
for j in range(0, len(array) - i - 1):
# compare two adjacent elements
# change > to < to sort in descending order
if array[j] > array[j + 1]:
# swapping elements if elements
# are not in the intended order
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
data = [-5, 72, 0, 33, -9]
bubbleSort(data)
print('Sorted Array in Ascending Order:')
print(data)
Bubble Sort Code in Java
import java.util.Arrays;
class Main {
// perform the bubble sort
static void bubbleSort(int array[]) {
int size = array.length;
// loop to access each array element
for (int i = 0; i < size - 1; i++)
// loop to compare array elements
for (int j = 0; j < size - i - 1; j++)
// compare two adjacent elements
// change > to < to sort in descending order
if (array[j] > array[j + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
public static void main(String args[]) {
int[] data = { -5, 72, 0, 33, -9 };
// call method using class name
Main.bubbleSort(data);
System.out.println("Sorted Array in Ascending Order:");
System.out.println(Arrays.to String(data));
}
}
Bubble Sort Code in C Programming
// Bubble sort in C
#include <stdio.h>
// perform the bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < size - 1; ++step) {
// loop to compare array elements
for (int i = 0; i < size - step - 1; ++i) {
// compare two adjacent elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
// print array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
int main() {
int data[] = {-5, 72, 0, 33, -9};
// find the array's length
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
printf("Sorted Array in Ascending Order:\n");
printArray(data, size);
}
Bubble Sort Code in C++
#include <iostream>
using namespace std;
// perform bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < size; ++step) {
// loop to compare array elements
for (int i = 0; i < size - step; ++i) {
// compare two adjacent elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping elements if elements
// are not in the intended order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
// print array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << array[i];
}
cout << "\n";
}
int main() {
int data[] = {-2, 45, 0, 11, -9};
// find array's length
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
cout << "Sorted Array in Ascending Order:\n";
printArray(data, size);
}
Optimized Bubble Sort in Python, Java, and C/C++
Optimized Bubble Sort in Python
def bubbleSort(array):
# loop through each element of array
for i in range(len(array)):
# keep track of swapping
swapped = False
# loop to compare array elements
for j in range(0, len(array) - i - 1):
# compare two adjacent elements
# change > to < to sort in descending order
if array[j] > array[j + 1]:
# swapping occurs if elements
# are not in the intended order
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
swapped = True
# no swapping means the array is already sorted
# so no need for further comparison
if not swapped:
break
data = [-5, 72, 0, 33, -9]
bubbleSort(data)
print('Sorted Array in Ascending Order:')
print(data)
Optimized Bubble Sort in Java
import java.util.Arrays;
class Main {
// perform the bubble sort
static void bubbleSort(int array[]) {
int size = array.length;
// loop to access each array element
for (int i = 0; i < (size-1); i++) {
// check if swapping occurs
boolean swapped = false;
// loop to compare adjacent elements
for (int j = 0; j < (size-i-1); j++) {
// compare two array elements
// change > to < to sort in descending order
if (array[j] > array[j + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swapped = true;
}
}
// no swapping means the array is already sorted
// so no need for further comparison
if (!swapped)
break;
}
}
public static void main(String args[]) {
int[] data = { -5, 72, 0, 33, -9 };
// call method using the class name
Main.bubbleSort(data);
System.out.println("Sorted Array in Ascending Order:");
System.out.println(Arrays.toString(data));
}
}
Optimized Bubble Sort in C Programming
#include
// perform the bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < size - 1; ++step) {
// check if swapping occurs
int swapped = 0;
// loop to compare array elements
for (int i = 0; i < size - step - 1; ++i) {
// compare two array elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[i]
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = 1;
}
}
// no swapping means the array is already sorted
// so no need for further comparison
if (swapped == 0) {
break;
}
}
}
// print array
void printArray(int array[], int size) {
For (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// main method
int main() {
int data[] = {-5, 72, 0, 33, -9};
// find the array's length
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
printf("Sorted Array in Ascending Order:\n");
printArray(data, size);
}
Optimized Bubble Sort in C++
#include
using namespace std;
// perform bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < (size-1); ++step) {
// check if swapping occurs
int swapped = 0;
// loop to compare two elements
for (int i = 0; i < (size-step-1); ++i) {
// compare two array elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping occurs if elements
// are not in intended order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = 1;
}
}
// no swapping means the array is already sorted
// so no need of further comparison
if (swapped == 0)
break;
}
}
// print an array
void printArray(int array[], int size) {
For (int i = 0; i < size; ++i) {
cout << " " << array[i];
}
cout << "\n";
}
int main() {
int data[] = {-5, 72, 0, 33, -9};
// find the array's length
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
cout << "Sorted Array in Ascending Order:\n";
printArray(data, size);
}
By now, you must have noticed that we left out one important part when explaining how the bubble sort works: the time complexity. The time complexity varies depending on which sorting algorithm is used, as well as the types of data. In short, if a sorting task takes very long in your programming language and you don’t mind losing some efficiency, try optimizing your bubble sort algorithms.
Choose The Right Software Development Program For You
This table compares various courses offered by Simplilearn, based on several key features and details. The table provides an overview of the courses' duration, skills you will learn, additional benefits, among other important factors, to help learners make an informed decision about which course best suits their needs.
Program Name Full Stack Java Developer Career Bootcamp Automation Testing Masters Program Post Graduate Program in Full Stack Web Development Geo IN All Non-US University Simplilearn Simplilearn Caltech Course Duration 11 Months 11 Months 9 Months Coding Experience Required Basic Knowledge Basic Knowledge Basic Knowledge Skills You Will Learn 15+ Skills Including Core Java, SQL, AWS, ReactJS, etc. Java, AWS, API Testing, TDD, etc. Java, DevOps, AWS, HTML5, CSS3, etc. Additional Benefits Interview Preparation
Exclusive Job Portal
200+ Hiring PartnersStructured Guidance
Learn From Experts
Hands-on TrainingCaltech CTME Circle Membership
Learn 30+ Tools and Skills
25 CEUs from Caltech CTMECost $$ $$ $$$ Explore Program Explore Program Explore Program
Wrapping It Up
In this article, you have learned what bubble sorting is and how you can write a C program for bubble sort in different ways. You can now put your knowledge to practice and hone your skills. To learn about more such fundamental C programming concepts, you can sign up for our SkillUp platform. The platform offers numerous free courses to help you learn and understand concepts of various programming languages, including C and C++.
Learning the fundamentals of a single programming language is not enough in today’s competitive world. Hence, it is vital to master multiple languages. You can opt for our Post Graduate Program for Full Stack Web Development for that. The certification course is a mixture of some of the most popular development languages in the world. By registering for the course, you get the chance to learn about multiple programming languages and relevant tools to land yourself a lucrative high-paying job in a multinational company.
If you have any doubts or queries regarding bubble sort using C programming, then feel free to post them in the comments section below. Our expert team will review them and get back to you with solutions at the earliest.