Bubble Sort in C Programming

Bubble sort is one of the simplest sorting algorithms that work by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items, and swapping them if they are in the wrong order. The pass through the list is repeated until the list is sorted. This algorithm is named for the way larger elements "bubble" to the top of the list.

What is Bubble Sort in C?

Bubble sort program in C is a straightforward algorithm that repeatedly traverses through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until no more swaps are needed, which means the list is sorted.

Pseudo Code for Bubble Sort in C

// Function to perform bubble sort
function bubbleSort(arr, n)
    // Loop through all elements in the array
    for i from 0 to n-1
        // Loop through the array from the beginning to the end of the unsorted part
        for j from 0 to n-i-1
            // Compare adjacent elements
            if arr[j] > arr[j+1]
                // Swap if they are in the wrong order
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
            end if
        end for
    end for
end function

// Function to print an array
function printArray(arr, size)
    for i from 0 to size-1
        print arr[i] + " "
    end for
    print newline
end function

// Main function to test the bubble sort algorithm
function main()
    arr = [64, 34, 25, 12, 22, 11, 90]
    n = length(arr)
    
    // Print the unsorted array
    print "Unsorted array:"
    printArray(arr, n)
    
    // Sort the array using bubble sort
    bubbleSort(arr, n)
    
    // Print the sorted array
    print "Sorted array:"
    printArray(arr, n)
end function

Explanation

1. bubbleSort function:

• The outer loop runs from i = 0 to n-1, indicating the passes over the entire array.
• The inner loop runs from j = 0 to n-i-1. This loop compares adjacent elements and swaps them if they are in the wrong order. The n-i-1 ensures that the already sorted elements at the end are not rechecked.
• The swapping involves a temporary variable temp to hold the value of arr[j] while arr[j] is assigned the value of arr[j+1], and arr[j+1] is assigned the value of temp.

2. printArray function:

• This function loops through the array and prints each element followed by a space. After the loop, a newline is printed for better readability.

3. main function:

• An array arr is initialized with some unsorted values.
• The size of the array n is calculated using a length function
• The unsorted array is printed using printArray.
• The array is then sorted using bubbleSort.
• Finally, the sorted array is printed using printArray.

Bubble Sort Visualisation

Bubble Sort Program in C Using For Loop

#include <stdio.h>

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

    // Bubble Sort using for loop
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap arr[j] and arr[j+1]
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }

    printf("Sorted array using for loop: \n");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Uses nested for loops to iterate through the array and perform swaps as necessary.

Bubble Sort Code in C Using While Loop

#include <stdio.h>

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

    // Bubble Sort using while loop
    while (i < n-1 && swapped) {
        swapped = 0;
        j = 0;
        while (j < n-i-1) {
            if (arr[j] > arr[j+1]) {
                // Swap arr[j] and arr[j+1]
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = 1;
            }
            j++;
        }
        i++;
    }

    printf("Sorted array using while loop: \n");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Utilizes a while loop with a swapped flag to continue sorting until no swaps are needed, indicating the array is sorted.

Bubble Sort Program in C Using Functions

#include <stdio.h>

// Function to perform bubble sort
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap arr[j] and arr[j+1]
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; 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);
    
    // Sort the array using bubble sort function
    bubbleSort(arr, n);

    printf("Sorted array using function: \n");
    printArray(arr, n);

    return 0;
}

Encapsulates the bubble sort logic within a bubbleSort function and a printArray function for printing the array before and after sorting. The main function calls these to demonstrate sorting.

Bubble Sort Program in C Using Pointers

#include <stdio.h>

void Bubble_sort(int *arr, int n) { //array passed as pointer
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if ( *(arr + j) > *(arr + j + 1)) {
        //swapping of array elements using pointers
        int temp = *(arr + j);
        *(arr + j) = *(arr + j + 1);
        *(arr + j + 1) = temp;
      }
    }
  }
  printf("Array after implementing Bubble sort: ");
  for (int i = 0; i < n; i++) {
    printf("%d  ", *(arr + i));
  }
}

int main() {
  int n = 5;
  int arr[5] = {100, 400, 200, 500, 300};
  Bubble_sort(arr, n);
  return 0;
}

In the Bubble_sort function, array elements are compared and swapped using pointer arithmetic (*(arr + j)), ensuring in-place sorting. The sorted array is then printed using pointer dereferencing in a loop. This approach highlights the use of pointers for array operations, making the code more versatile and efficient in memory usage.

Optimised Implementation of Bubble Sort Algorithm in C

#include <stdio.h>
#include <stdbool.h>

int main() {
  int n = 5;
  int arr[5] = {44, 33, 11, 22, 55};

  for (int i = 0; i < n - 1; i++) {
    bool flag = false;
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        flag = true; //Elements swapped in this pass
      }
    }
    //if flag == false, no swapping is done in this pass
    if (flag == false) break; //Array is already sorted, hence break the loop
  }
  printf("Array after implementing Bubble sort in an optimised way: ");
  for (int i = 0; i < n; i++) {
    printf("%d  ", arr[i]);
  }
  return 0;
}

Introducing a flag to track if any elements were swapped during each pass. If no swaps occur (flag remains false), the array is already sorted, and the loop breaks early, reducing unnecessary iterations. This optimization improves efficiency for nearly sorted arrays. The final sorted array is then printed.

As we have observed in the above example codes, even if the array is sorted after some passes, it continues to check (n-1) times which is not an optimized way of executing an algorithm.

We can reduce the execution time by optimizing the algorithm so that it will have best-case time complexity of O(n) when the array is sorted.

Time and Space Complexity of Bubble Sort

Best Case Time Complexity: O(n) - Occurs when the array is already sorted; requires one pass with no swaps.

Average and Worst Case Time Complexity: O(n2)O(n^2)O(n2): Due to quadratic growth in comparisons and swaps as the array size increases, typical in random or reverse-ordered arrays.

Space Complexity: O(1) - Bubble sort is an in-place algorithm, requiring only a constant amount of additional memory for temporary variables.

Key Points of Bubble Sorting in C

• Simple and Easy to Implement: Bubble sort is one of the simplest sorting algorithms and is very easy to understand and implement.
• Inefficient for Large Datasets: It has a worst-case and average-case time complexity of \(O(n^2)\), which makes it inefficient for large datasets.
• In-Place Algorithm: It does not require any additional storage space as it operates directly on the original array.
• Stable Sort: Bubble sort is a stable sorting algorithm because it does not change the relative order of elements with equal keys.

Applications of Bubble Sorting Program in C

• Small Datasets: Sorting small arrays or lists where simplicity and ease of implementation are prioritized over efficiency.
• Ad Hoc Sorting: Quick sorting needs in situations where other algorithms might be too complex or unnecessary.

Learn more about C programming language from our latest blog “History of C Language”

Conclusion

Bubble sort in C is an excellent way to get started with learning sorting algorithms due to its simplicity and ease of implementation. While it may not be the most efficient for large datasets, it is a valuable educational tool for understanding the basic principles of sorting.

With the provided code and explanation, you should now have a solid understanding of how to implement and work with bubble sort in C.

For those looking to advance their skills beyond basic algorithms, consider enrolling in AlmaBetter's full stack developer course with the pay after placement opportunity. This can provide a comprehensive learning experience, ensuring you gain expertise in a wide range of technologies and secure a job before having to pay for your education.