Bubble Sort in C: Understanding the Basics and Beyond

If you’ve ever worked with data, you know that sorting it into a specific order is super important. Whether you're arranging numbers from smallest to largest or sorting words alphabetically, sorting algorithms make this happen. One of the most basic, and often misunderstood, sorting algorithms is bubble sort in C.

Now, don’t let its simplicity fool you. While it’s not the fastest algorithm out there, bubble sort in C is a great starting point for understanding sorting, comparisons, and swaps. Even, all top-notch software development courses have this algorithm covered. It’s perfect for small datasets and an awesome tool when you’re just learning about algorithms.

In this blog, we’ll take a closer look at how bubble sort in C works, its pros and cons, and when it might still be useful. Stick around if you want to get a better grip on this classic algorithm.

What is Bubble Sort in C Programming?

Bubble Sort is a simple yet inefficient sorting algorithm used in C programming to arrange a list of elements in a particular order, typically ascending. It gets its name from the way smaller elements "bubble" to the top (beginning) of the list, and larger elements sink to the bottom (end) with each pass through the array. This sorting algorithm works by repeatedly comparing adjacent elements in the list and swapping them if they are in the wrong order.

Must Explore: Introduction to C Tutorial

The bubble sort in C works like this:

1. Comparison and Swap: Start at the beginning of the list and compare the first two elements. If the first element is larger than the second, swap them.

2. Continue Through the List: Move to the next pair of adjacent elements and repeat the process. After the first full pass through the list, the largest element will have "bubbled" to the correct position at the end of the list.

3. Repeat the Process: After each pass, reduce the number of elements being considered for sorting since the largest elements are already in their correct positions. Repeat the comparison and swap process for the remaining unsorted elements.

4. Termination: The algorithm stops when a full pass through the list occurs without any swaps, indicating that the list is sorted.

Although bubble sort in C is intuitive and easy to implement, it’s not the most efficient sorting algorithm. Its time complexity in the average and worst-case scenarios is O(n²), meaning its performance degrades rapidly as the number of elements grows. This makes it a poor choice for sorting large datasets but a good learning tool for understanding the basics of sorting algorithms.

Must Read: 29 C Programming Projects in 2025 for All Levels [Source Code Included]

Key Characteristics of Bubble Sort in C:

• In-place Sorting: Bubble Sort does not require additional memory space apart from the array itself, making it memory efficient.
• Stable Sorting: Bubble Sort is stable, meaning that it preserves the relative order of equal elements in the array.
• Best Case Performance: If the list is already sorted, the algorithm can complete in O(n) time by detecting that no swaps are needed during the iteration.

Also Explore: What are Data Structures in C & How to Use Them?

How C Programming Works for Bubble Sort

Bubble Sort in C is a straightforward sorting algorithm that compares adjacent elements in an array and swaps them if they are in the wrong order. This process repeats until the array is sorted. While it's simple to implement and understand, Bubble Sort is not the most efficient algorithm for large datasets due to its high time complexity.

Key Steps in the Bubble Sort Process:

1. Initialization:

The array to be sorted is defined, and we start by setting up the basic structure for the sorting algorithm.

2. Outer Loop:

The outer loop controls the number of passes through the array. Each pass guarantees that the largest unsorted element moves to the correct position at the end of the list.

3. Inner Loop:

The inner loop compares adjacent elements and swaps them if they are out of order. With each pass of the outer loop, the number of elements to be compared reduces because the largest elements are "bubbled" to the end.

4. Swapping Elements:

If two adjacent elements are in the wrong order, they are swapped using a temporary variable.

5. Optimization (Early Termination):

A flag (`swapped`) is used to detect if any swaps were made during the inner loop. If no swaps occur during a pass, the algorithm can terminate early, improving efficiency in the best-case scenario (when the array is already sorted).

Check out the Executive Diploma in Data Science & AI with IIIT-B!

Example Code for Bubble Sort in C:

Here's a simple C program to implement Bubble Sort:

#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j, temp;
int swapped;
// Outer loop for each pass
for (i = 0; i < n - 1; i++) {
swapped = 0; // Reset swapped flag for this pass
// Inner loop for comparing adjacent elements
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements if they're in the wrong order
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1; // Mark that a swap was made
}
}
// If no elements were swapped, the array is sorted
if (swapped == 0)
break;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted Array: \n");
printArray(arr, n);
bubbleSort(arr, n);
printf("Sorted Array: \n");
printArray(arr, n);
return 0;
}

Explanation of Code:

1. Initialization:

The array `arr[]` is initialized with the values `{64, 34, 25, 12, 22, 11, 90}`, and the size of the array is calculated with `sizeof(arr) / sizeof(arr[0])`.

2. Outer Loop:

The outer loop (`for (i = 0; i < n - 1; i++)`) controls the number of passes needed to sort the array. The loop runs `n-1` times, where `n` is the number of elements in the array.

3. Inner Loop:

The inner loop (`for (j = 0; j < n - i - 1; j++)`) compares adjacent elements and swaps them if they are out of order. The range of the inner loop reduces with each pass because the largest elements are already sorted at the end of the array.

4. Swapping:

The swapping mechanism uses a temporary variable `temp` to store one of the values during the swap, ensuring the elements are correctly swapped.

5. Optimization (Early Termination):

The `swapped` flag is set to `1` whenever a swap occurs. If no swaps happen during a full pass (i.e., the array is already sorted), the loop breaks early, improving efficiency.

Output of the Program:

Given the array `{64, 34, 25, 12, 22, 11, 90}`, the output of the program would be:

Unsorted Array:

64 34 25 12 22 11 90

Sorted Array:

11 12 22 25 34 64 90

Step-by-Step Breakdown of the Sorting Process:

First Pass (i = 0):

Compare `arr[0]` (64) and `arr[1]` (34): Swap them.

Array: `{34, 64, 25, 12, 22, 11, 90}`

Compare `arr[1]` (64) and `arr[2]` (25): Swap them.

Array: `{34, 25, 64, 12, 22, 11, 90}`

Compare `arr[2]` (64) and `arr[3]` (12): Swap them.

Array: `{34, 25, 12, 64, 22, 11, 90}`

Compare `arr[3]` (64) and `arr[4]` (22): Swap them.

Array: `{34, 25, 12, 22, 64, 11, 90}`

Compare `arr[4]` (64) and `arr[5]` (11): Swap them.

Array: `{34, 25, 12, 22, 11, 64, 90}`

Compare `arr[5]` (64) and `arr[6]` (90): No swap needed.

After the first pass, 90 is in its correct position.

Array: `{34, 25, 12, 22, 11, 64, 90}`

Second Pass (i = 1):

Compare `arr[0]` (34) and `arr[1]` (25): Swap them.

Array: `{25, 34, 12, 22, 11, 64, 90}`

Compare `arr[1]` (34) and `arr[2]` (12): Swap them.

Array: `{25, 12, 34, 22, 11, 64, 90}`

Compare `arr[2]` (34) and `arr[3]` (22): Swap them.

Array: `{25, 12, 22, 34, 11, 64, 90}`

Compare `arr[3]` (34) and `arr[4]` (11): Swap them.

Array: `{25, 12, 22, 11, 34, 64, 90}`

Compare `arr[4]` (34) and `arr[5]` (64): No swap needed.

After the second pass, 64 is in its correct position.

Array: `{25, 12, 22, 11, 34, 64, 90}`

Third Pass (i = 2):

Compare `arr[0]` (25) and `arr[1]` (12): Swap them.

Array: `{12, 25, 22, 11, 34, 64, 90}`

Compare `arr[1]` (25) and `arr[2]` (22): Swap them.

Array: `{12, 22, 25, 11, 34, 64, 90}`

Compare `arr[2]` (25) and `arr[3]` (11): Swap them.

Array: `{12, 22, 11, 25, 34, 64, 90}`

Compare `arr[3]` (25) and `arr[4]` (34): No swap needed.

After the third pass, 34 is in its correct position.

Array: `{12, 22, 11, 25, 34, 64, 90}`

The process continues, and after a few more passes, the array will be fully sorted:

{11, 12, 22, 25, 34, 64, 90}

Pursue DBA in Digital Leadership from Golden Gate University, San Francisco!

Pseudo Code for Bubble Sort in C

Once you go through the pseudo coed of bubble sort in C, you’’ understand the essence of this algorithm. It’ll help you implement it not only in C, but in another programming language also.

BubbleSort(arr, n):

for i = 0 to n-1 do:

swapped = false

for j = 0 to n-i-2 do:

if arr[j] > arr[j+1] then:

Swap arr[j] and arr[j+1]

swapped = true

if swapped is false then:

break

Check out the Executive Diploma in Data Science & AI with IIIT-B!

Explanation of Pseudo Code of Bubble Sort in C:

1. Outer Loop (`for i = 0 to n-1`):

The outer loop iterates through the array multiple times, ensuring that the largest elements "bubble up" to their correct position with each pass. Further, after each complete pass, the largest element will have been correctly placed at the end of the array.

2. Inner Loop (`for j = 0 to n-i-2`):

The inner loop compares adjacent elements of the array (`arr[j]` and `arr[j+1]`) and swaps them if they are in the wrong order.

The number of comparisons decreases with each iteration of the outer loop because the largest elements are already placed at the end.

3. Swapping (`Swap arr[j] and arr[j+1]`):

If the element at `arr[j]` is greater than the element at `arr[j+1]`, they are swapped

4. Early Termination (`if swapped is false then break`):

If no elements were swapped in a pass, this means the array is already sorted, and the algorithm terminates early, reducing unnecessary comparisons.

Implementation of Bubble Sort in C

Before you start with implementation, you need to understand the following concepts in C programming:

• For Loop in C
• Functions in C
• Pointers in C
• While Loop in C

Bubble Sort in C Using For Loop

Bubble sort in C can be easily implemented using `for` loops, which allow us to efficiently control the iterations through the array. The `for` loop works perfectly here because it can track the number of passes and manage adjacent element comparisons for each pass.

Using `for` loops for bubble sort in C ensures that both the outer and inner loops are managed effectively, simplifying the sorting process.

1. Outer Loop:

The outer loop handles the number of passes through the array. With each pass, the largest unsorted element "bubbles" to the end of the array. This loop runs `n-1` times, where `n` is the number of elements in the array.

2. Inner Loop:

The inner loop compares each pair of adjacent elements and swaps them if necessary. After each pass, the number of comparisons decreases because the largest elements get moved to the end of the array.

3. Early Termination:

A `swapped` flag is used to detect whether any swaps occurred during the inner loop. If no swaps were made, the array is already sorted, and the algorithm terminates early, improving efficiency.

Example Code for Bubble Sort Using `For` Loop:

#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j, temp;
int swapped;
// Outer loop for each pass
for (i = 0; i < n - 1; i++) {
swapped = 0; // Reset swapped flag for this pass
// Inner loop for comparing adjacent elements
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements if they're in the wrong order
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1; // Mark that a swap was made
}
}
// If no elements were swapped, the array is sorted
if (swapped == 0)
break;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted Array: \n");
printArray(arr, n);
bubbleSort(arr, n);
printf("Sorted Array: \n");
printArray(arr, n);
return 0;
}

Explanation of the Code:

1. Array Initialization:

The array `arr[]` is initialized with values `{64, 34, 25, 12, 22, 11, 90}`. The number of elements in the array is determined by `sizeof(arr) / sizeof(arr[0])`.

2. Outer Loop:

The outer `for` loop iterates `n-1` times. During each iteration, the largest unsorted element is moved to its correct position at the end of the array.

3. Inner Loop:

The inner `for` loop compares each adjacent pair of elements and swaps them if necessary. After each pass, the unsorted portion of the array decreases because the largest element is now at the correct position at the end.

4. Swapping Elements:

Elements are swapped using a temporary variable `temp` when they are out of order.

5. Optimization (Early Termination):

If no swaps occur during a pass, it indicates that the array is already sorted, so the algorithm breaks out of the outer loop early, saving time.

6. Printing the Array:

The `printArray` function is used to display the array before and after sorting.

Output of the Program:

For the input array `{64, 34, 25, 12, 22, 11, 90}`, the output will be:

Unsorted Array:

64 34 25 12 22 11 90

Sorted Array:

11 12 22 25 34 64 90

Bubble Sort in C Using While Loop

Bubble sort in C can also be implemented using a `while` loop. While loops are particularly useful when you want to iterate until a certain condition is met, such as when no more swaps are required, indicating that the array is sorted.

In this section, we'll implement bubble sort in C using a `while` loop and explain how it differs slightly from the `for` loop implementation.

Furthermore, the bubble sort in C algorithm still works the same way, but the key difference here is that we will use a `while` loop to control the outer loop, which will continue until no more swaps are made during a pass through the array.

The core steps include:

1. Outer Loop:

The outer `while` loop runs as long as swaps are made during the inner loop. If no swaps are made in a particular pass, the algorithm terminates early, improving efficiency.

2. Inner Loop:

The inner loop compares adjacent elements and swaps them if necessary. This inner loop remains the same as in the `for` loop version.

3. Optimization (Early Termination):

A `swapped` flag is used to determine if any swaps occurred during the inner loop. If no swaps happen during a full pass, the outer loop terminates early.

Example Code for Bubble Sort in C Using `While` Loop:

#include <stdio.h>

void bubbleSort(int arr[], int n) {
int i, j, temp;
int swapped;

// Outer loop using a while loop
i = 0;
while (i < n - 1) {
swapped = 0; // Reset swapped flag for this pass

// Inner loop for comparing adjacent elements
j = 0;
while (j < n - i - 1) {
if (arr[j] > arr[j + 1]) {
// Swap elements if they're in the wrong order
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;

swapped = 1; // Mark that a swap was made
}
j++;
}

// If no elements were swapped, the array is sorted
if (swapped == 0)
break;

i++;
}
}

void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Unsorted Array: \n");
printArray(arr, n);

bubbleSort(arr, n);

printf("Sorted Array: \n");
printArray(arr, n);

return 0;
}

Explanation of Code:

1. Array Initialization:

The array `arr[]` is initialized with the values `{64, 34, 25, 12, 22, 11, 90}`. The number of elements in the array is calculated using `sizeof(arr) / sizeof(arr[0])`, which gives `7` in this case.

2. Outer Loop:

The outer `while` loop runs until `i` reaches `n-1` (the number of elements minus one). If no swaps are made during a full pass (i.e., the array is already sorted), the loop terminates early, reducing unnecessary passes.

3. Inner Loop:

The inner `while` loop compares each adjacent element `arr[j]` and `arr[j + 1]`. If the element at `arr[j]` is greater than the element at `arr[j + 1]`, they are swapped.

4. Swapping Elements:

The elements are swapped using a temporary variable `temp`, which holds one of the values during the swap, ensuring that the elements are correctly exchanged.

5. Optimization (Early Termination):

If no swaps occur during a full pass of the inner loop, it means the array is already sorted, and the outer loop breaks early. This optimization improves performance in cases where the array is nearly or already sorted.

6. Printing the Array:

The `printArray` function is used to print the array before and after sorting.

Output of the Program:

Given the input array `{64, 34, 25, 12, 22, 11, 90}`, the output of the program will be:

Unsorted Array:

64 34 25 12 22 11 90

Sorted Array:

11 12 22 25 34 64 90

Bubble Sort in C Using Functions

Bubble sort in C can be modularized by using functions. By breaking down the sorting process into smaller functions, we make the code more reusable, readable, and easier to maintain. Using functions in C allows us to separate concerns like swapping elements, printing the array, and performing the sorting itself, which improves code organization.

Further, the bubble sort in C remains the same, but we will divide the tasks into three distinct functions:

1. swap():

A function responsible for swapping two elements of the array.

2. bubbleSort():

The main function that implements the Bubble Sort algorithm. This function will call `swap()` as needed.

3. printArray():

A function to print the array before and after the sorting process.

This approach enhances the structure and readability of the code, especially when we have larger programs.

Example Code for Bubble Sort Using Functions:

#include <stdio.h>

// Function to swap two elements
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Function to perform Bubble Sort
void bubbleSort(int arr[], int n) {
int i, j;
int swapped;

// Outer loop for each pass
for (i = 0; i < n - 1; i++) {
swapped = 0; // Reset swapped flag for this pass

// Inner loop for comparing adjacent elements
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Call swap function if elements are in the wrong order
swap(&arr[j], &arr[j + 1]);
swapped = 1; // Mark that a swap was made
}
}

// If no elements were swapped, the array is sorted
if (swapped == 0)
break;
}
}

// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Unsorted Array: \n");
printArray(arr, n);

bubbleSort(arr, n);

printf("Sorted Array: \n");
printArray(arr, n);

return 0;
}

Explanation of Code:

1. swap() Function:

This function takes two integer pointers as parameters (`a` and `b`) and swaps their values using a temporary variable `temp`. It’s a helper function that makes the swapping process more organized and reusable throughout the code.

2. bubbleSort() Function:

This function is responsible for implementing the Bubble Sort algorithm. It contains the outer loop, which ensures that we perform `n-1` passes over the array, and the inner loop, which compares adjacent elements and calls the `swap()` function when necessary. If no swaps occur during a pass, it breaks out of the loop early to optimize the sorting process.

3. printArray() Function:

This function simply prints the array elements, separated by spaces. It's useful for displaying the state of the array before and after sorting.

4. main() Function:

The main function initializes the array `arr[]`, calculates its size, and calls the `printArray()` function to show the unsorted array. It then calls `bubbleSort()` to sort the array and prints the sorted array.

Also, learn about static functions and user-defined function in C.

Output of the Program:

For the input array `{64, 34, 25, 12, 22, 11, 90}`, the output will be:

Unsorted Array:

64 34 25 12 22 11 90

Sorted Array:

11 12 22 25 34 64 90

Bubble Sort in C Using Pointers

In C, pointers offer a powerful way to manipulate memory directly, which can be very useful for sorting algorithms. Bubble sort in C can be implemented using pointers to directly access and manipulate the elements of the array. By using pointers, we can enhance the code by providing a different approach to swap elements, making the code more flexible and potentially more efficient in some scenarios.

We'll implement bubble sort in C using pointers to swap elements and compare adjacent array elements.

The core working of bubble sort in C using pointers follows the below procedure:

1. Pointer Arithmetic:

Pointers in C allow us to use pointer arithmetic to access array elements. By using a pointer to the array, we can increment the pointer to traverse the array and compare adjacent elements.

2. Swapping with Pointers:

Swapping elements will also be done using pointer dereferencing. The use of pointers for swapping offers a clearer demonstration of how C interacts with memory directly.

3. Optimization (Early Termination):

The **Bubble Sort** algorithm will still use the optimization of early termination if no swaps are made during a pass through the array.

Example Code for Bubble Sort Using Pointers:

#include <stdio.h>

// Function to swap two elements using pointers
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Function to perform Bubble Sort using pointers
void bubbleSort(int *arr, int n) {
int i, j;
int swapped;

// Outer loop for each pass
for (i = 0; i < n - 1; i++) {
swapped = 0; // Reset swapped flag for this pass

// Inner loop for comparing adjacent elements
for (j = 0; j < n - i - 1; j++) {
// Use pointer arithmetic to compare adjacent elements
if (*(arr + j) > *(arr + j + 1)) {
// Call swap function using pointers if elements are in the wrong order
swap(arr + j, arr + j + 1);
swapped = 1; // Mark that a swap was made
}
}

// If no elements were swapped, the array is sorted
if (swapped == 0)
break;
}
}

// Function to print the array
void printArray(int *arr, int n) {
for (int i = 0; i < n; i++) {
printf("%d ", *(arr + i)); // Use pointer arithmetic to print each element
}
printf("\n");
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Unsorted Array: \n");
printArray(arr, n);

bubbleSort(arr, n);

printf("Sorted Array: \n");
printArray(arr, n);

return 0;
}

Explanation of Code:

1. swap() Function:

This function swaps two elements in the array using pointers. The function takes two pointers `a` and `b` and dereferences them to swap the values they point to. It uses a temporary variable `temp` to hold one value while the swap is taking place.

2. bubbleSort() Function:

The `bubbleSort()` function performs the Bubble Sort algorithm. It works by comparing adjacent elements in the array using pointer arithmetic. The `*(arr + j)` expression is used to access the value at index `j`. If the elements are out of order, they are swapped using the `swap()` function, which operates on pointers.

3. Pointer Arithmetic:

The line `*(arr + j)` is used instead of `arr[j]` to access the elements of the array. The `arr` pointer points to the beginning of the array, and adding an integer `j` to the pointer moves it to the `j`th element. The dereference operator `*` then retrieves the value stored at that memory location.

4. printArray() Function:

The `printArray()` function prints the array using pointer arithmetic. By dereferencing `arr + i`, we print each element in the array.

5. main() Function:

The main function initializes the array `arr[]`, calculates its size using `sizeof()`, and calls `printArray()` to show the unsorted array. It then calls `bubbleSort()` to sort the array and prints the sorted array.

Also explore the most advanced course in artificial intelligence and machine learning.

Output of the Program:

For the input array `{64, 34, 25, 12, 22, 11, 90}`, the output will be:

Unsorted Array:

64 34 25 12 22 11 90

Sorted Array:

11 12 22 25 34 64 90

C Program for Optimized Implementation of Bubble Sort Algorithm

While the standard implementation of bubble sort in C repeatedly compares adjacent elements and swaps them if necessary, it is not the most efficient algorithm for larger datasets. The Optimized Bubble Sort improves upon the basic algorithm by introducing an important modification: it stops the algorithm early if no swaps are made during a full pass through the array.

This optimization helps reduce unnecessary iterations when the array becomes partially or fully sorted before the algorithm completes all of its passes.

Key Optimizations of Bubble Sort in C:

1. Early Termination:

If no elements were swapped during a pass through the array, it indicates that the array is already sorted. Therefore, the algorithm can terminate early without performing additional passes, improving efficiency.

2. Reduced Range for Inner Loop:

After each pass, the largest element gets moved to the correct position at the end of the array. This means that the number of comparisons needed can be reduced with each subsequent pass, as the last elements are already sorted.

Also pursue deep insights to digital marketing and grow your career.

Example Code for Optimized Bubble Sort in C:

#include <stdio.h>

// Function to perform Optimized Bubble Sort
void optimizedBubbleSort(int arr[], int n) {
int i, j, temp;
int swapped;

// Outer loop for each pass
for (i = 0; i < n - 1; i++) {
swapped = 0; // Reset swapped flag for this pass

// Inner loop for comparing adjacent elements
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements if they are in the wrong order
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;

swapped = 1; // Mark that a swap was made
}
}

// If no elements were swapped, the array is already sorted
if (swapped == 0) {
break; // Exit early as the array is sorted
}
}
}

// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Unsorted Array: \n");
printArray(arr, n);

optimizedBubbleSort(arr, n);

printf("Sorted Array: \n");
printArray(arr, n);

return 0;
}

Explanation of Code:

1. optimizedBubbleSort() Function:

This function implements the Optimized Bubble Sort in C algorithm. The outer loop iterates over the array for each pass, and the inner loop compares adjacent elements. If a swap is necessary, the elements are swapped, and a `swapped` flag is set to `1`.

2. Early Termination:

If no swaps are made during an entire pass through the array (i.e., `swapped == 0`), the array is already sorted, and the algorithm breaks out of the loop early, preventing unnecessary further passes.

3. Inner Loop Range Reduction:

As the largest elements "bubble up" to the end of the array during each pass, the range for the inner loop (`n - i - 1`) is reduced, meaning that fewer comparisons are made in subsequent passes.

4. printArray() Function:

This function is used to print the array before and after sorting.

5. main() Function:

In the main function, an array `arr[]` is initialized, and the size of the array is calculated using `sizeof(arr) / sizeof(arr[0])`. The unsorted array is printed, then sorted using the `optimizedBubbleSort()` function, and the sorted array is printed.

Output of the Program:

For the input array `{64, 34, 25, 12, 22, 11, 90}`, the output will be:

Unsorted Array:

64 34 25 12 22 11 90

Sorted Array:

11 12 22 25 34 64 90

How the Optimization Improves Bubble Sort in C:

Let’s look at all the aspects, contributing to optimize bubble sort in C programming.

1. Early Termination:

The biggest optimization in this version of Bubble Sort is the early termination feature. If, after a full pass through the array, no swaps were made, the algorithm can exit early, reducing the overall number of passes. For example, if the array is already sorted or nearly sorted, this will save a lot of unnecessary work.

2. Reduced Inner Loop Range:

With each pass, the largest element is moved to its correct position, meaning the inner loop can skip over the last elements that are already in their correct position. This also reduces the number of comparisons needed on subsequent passes.

Complexity of Bubble Sort in C Programming

Bubble sort in C is a simple sorting algorithm, but it is not the most efficient one when compared to others like Quick Sort, Merge Sort, or even Insertion Sort. Nonetheless, it is useful in educational contexts to demonstrate basic sorting concepts. Let's break down the time complexity of Bubble Sort and its behavior under different scenarios.

1. Time Complexity of Bubble Sort:

Best Case: O(n)

The best case occurs when the array is already sorted.

• In this case, the algorithm will only make one pass through the array without performing any swaps.
• With the **optimized version** of Bubble Sort (where the algorithm terminates early if no swaps are made), it will detect that no swaps have been made during the first pass and terminate early.
• Hence, the time complexity for the best case is **O(n)**, where `n` is the number of elements in the array.

Average Case: O(n²)

The average case of bubble sort in C represents the scenario where the elements are in random order.

• In this case, the algorithm will perform multiple passes over the array. On each pass, it compares adjacent elements and performs swaps if necessary.
• Even though some swaps will occur, the algorithm still needs to perform comparisons for every adjacent pair in the array.
• For each element, we need to compare it with other elements, which gives a time complexity of O(n²).

Worst Case: O(n²)

The worst case of bubble sort in C occurs when the array is sorted in reverse order (completely reversed).

• In this scenario, the algorithm will need to compare and swap every pair of adjacent elements.
• For the first pass, it will compare `n-1` pairs, for the second pass `n-2` pairs, and so on until only one comparison is left in the last pass.
• The total number of comparisons made is the sum of the first `n-1` integers: `n-1 + n-2 + ... + 1`, which sums up to O(n²).

Space Complexity: O(1)

Bubble Sort is an **in-place sorting algorithm**, meaning it does not require extra space beyond the input array. All operations are done within the array itself, and no additional data structures are needed.

Thus, the space complexity of Bubble Sort is O(1).

Breakdown of Time Complexity with Respect to Loops:

Outer Loop (i loop):

This loop runs `n-1` times in the worst case, where `n` is the number of elements in the array.

Inner Loop (j loop):

For each iteration of the outer loop, the inner loop performs comparisons between adjacent elements. The inner loop runs `n-i-1` times for each pass (since elements are gradually getting sorted in each pass).

Therefore, for the first pass, it runs `n-1` times, for the second pass, it runs `n-2` times, and so on, until the last pass, which runs only once.

The total number of comparisons made by both loops is the sum of the first `n-1` integers, which gives a time complexity of **O(n²)**.

Visualization of Complexity of Bubble Sort in C:

Best Case (already sorted array):

Outer Loop runs: 1 time

Inner Loop runs: n-1 times, but terminates early as no swaps happen

Total Complexity: O(n)

Average Case (randomly shuffled array):

Outer Loop runs: n-1 times

Inner Loop runs: n-1, n-2, n-3, ..., 1 times

Total Complexity: O(n²)

Worst Case (array is sorted in reverse order):

Outer Loop runs: n-1 times

Inner Loop runs: n-1, n-2, n-3, ..., 1 times

Total Complexity: O(n²)

The Best Use Case of Bubble Sort in C for Real-World Applications

Conclusion

So, to wrap it up, Bubble Sort in C is a simple and easy-to-understand sorting algorithm, but it’s not the fastest when dealing with large datasets. It’s perfect for small datasets, educational purposes, and cases where the array is already partially sorted. It’s also great when you need stable sorting, meaning equal elements stay in their original order.

While it might not be the go-to for big data, Bubble Sort in C still has its place when you value simplicity or need quick, straightforward sorting for small tasks. Overall, it’s a great algorithm to learn, but for more serious applications, you’d want to explore faster sorting methods.

FAQs

1. Can Bubble Sort be used for sorting strings in C?

Yes, Bubble Sort can be used to sort strings in C. You just need to compare each character in the strings, and if necessary, swap them. This would work in much the same way as sorting an array of numbers, but instead of comparing numerical values, you compare the strings lexicographically.

2. What is the space complexity of Bubble Sort?

The space complexity of Bubble Sort is O(1). This is because Bubble Sort is an in-place sorting algorithm, meaning it doesn’t require any additional space for sorting beyond the input array.

3. What happens if Bubble Sort encounters an already sorted array?

If Bubble Sort encounters an already sorted array and is optimized with early termination, it will detect that no swaps are needed and stop after the first pass, making it run in O(n) time instead of O(n²). Without early termination, it would still perform O(n²) comparisons, even though the array is already sorted.

4. Can Bubble Sort be used to sort linked lists in C?

Technically, Bubble Sort can be applied to a linked list, but it's not ideal. Sorting a linked list with Bubble Sort would involve rearranging the nodes by changing pointers instead of swapping elements. This makes Bubble Sort less efficient and more complex to implement compared to other algorithms like Merge Sort, which works better with linked lists.

5. How does Bubble Sort compare to Insertion Sort?

While both Bubble Sort and Insertion Sort have O(n²) time complexity in the worst case, Insertion Sort is generally more efficient. Insertion Sort tends to perform fewer swaps, especially when the data is already partially sorted. Bubble Sort, on the other hand, might still perform unnecessary comparisons even if the array is nearly sorted.

6. Why is Bubble Sort not commonly used for large datasets?

Bubble Sort is not commonly used for large datasets because its time complexity of O(n²) makes it inefficient. As the dataset grows, the number of comparisons and swaps increases dramatically, making it significantly slower than more efficient algorithms like Quick Sort or Merge Sort, which can handle larger datasets more efficiently.

7. What’s the worst-case scenario for Bubble Sort in C?

The worst-case scenario for Bubble Sort occurs when the array is sorted in reverse order. In this case, Bubble Sort will need to perform the maximum number of comparisons and swaps, leading to a time complexity of O(n²).

8. How does the number of passes change with Bubble Sort?

The number of passes in Bubble Sort decreases as elements are sorted. Initially, it requires n-1 passes, where n is the number of elements. However, with each pass, the largest element is moved to its correct position, so the next pass only needs to check the remaining unsorted elements.

9. Is Bubble Sort in C used in competitive programming?

Bubble Sort is rarely used in competitive programming due to its inefficiency for large datasets. More advanced sorting algorithms like Quick Sort or Merge Sort are preferred in competitive programming because they offer faster performance with larger datasets. However, Bubble Sort might be used in simple problems or for educational purposes.

10. Can Bubble Sort in C be parallelized?

In theory, parts of Bubble Sort could be parallelized, especially during comparisons and swaps. However, due to the nature of the algorithm (adjacent element comparison), effectively parallelizing it would be complex and might not result in significant performance improvement compared to other parallel sorting algorithms like Merge Sort or Quick Sort.

11. Can Bubble Sort in C sort objects or custom data structures?

Yes, Bubble Sort can be adapted to sort objects or custom data structures, as long as a way to compare the objects exists. For example, if you’re sorting an array of structs, you can define a comparison function to compare the relevant fields of the structs, and Bubble Sort will work similarly as it does with primitive types like integers.

Take a Free C Programming Quiz

Answer quick questions and assess your C programming knowledge

Start Quiz