Implementation of Bubble Sort Algorithm in C

Bubble sort is a basic algorithm used to sort a list of items by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. In this article, we’ll implement a basic version of the bubble sort algorithm in C programming language which can sort a given list of numbers in ascending order. We’ll then explore several practical variations, including sorting in descending order and sorting custom structures.

Prerequisites:

Basic Bubble Sort Implementation

Let’s start with the standard iterative implementation of bubble sort. This version sorts an array in ascending order by repeatedly comparing adjacent elements and swapping them if they are in the wrong order.

#include <stdio.h>

void bubbleSort(int arr[], int n) {
  // `arr` is the array that we want to sort
  // `n` is the number of elements in the array

  // The outer loop goes through each element in the array
  // After each pass, the largest unsorted element is placed at the end
  for (int i = 0; i < n - 1; i++) {

    // The inner loop compares each adjacent element and swaps them if needed
    // As the largest element is bubbled to end with each outer loop, we exclude the sorted elements from comparison using `n-i-1`
    for (int j = 0; j < n - i - 1; j++) {

      // Compare the adjacent elements
      // If the first element is larger than the second element then swap
      if (arr[j] > arr[j + 1]) {
        // Swap arr[j] and arr[j+1] using a temporary variable
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

// Utility function to print 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("Original array: ");
  printArray(arr, n);

  bubbleSort(arr, n);

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

  return 0;
}

Explanation:

  • We include the standard input/output library with #include <stdio.h>.
  • The bubbleSort function takes an integer array arr and its size n as input.
  • The outer loop for (int i = 0; i < n - 1; i++) iterates n-1 times.
  • The inner loop for (int j = 0; j < n - i - 1; j++) compares adjacent elements.
  • If arr[j] is greater than arr[j + 1], we swap them using a temporary variable temp.
  • The printArray function is used to print the array elements.
  • In the main function, we initialize an array, call bubbleSort, and then print the sorted array.

Sorting in Descending Order

To sort the array in descending order (from largest to smallest), we only need to change the comparison operator in the inner loop from > to <.

#include <stdio.h>

void bubbleSortDescending(int arr[], int n) {
  // `arr` is the array that we want to sort
  // `n` is the number of elements in the array

  // The outer loop goes through each element in the array
  // After each pass, the smallest unsorted element is placed at the end
  for (int i = 0; i < n - 1; i++) {

    // The inner loop compares each adjacent element and swaps them if needed
    for (int j = 0; j < n - i - 1; j++) {

      // Compare the adjacent elements
      // If the first element is smaller than the second element then swap
      if (arr[j] < arr[j + 1]) {
        // Swap arr[j] and arr[j+1] using a temporary variable
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

// Utility function to print 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("Original array: ");
  printArray(arr, n);

  bubbleSortDescending(arr, n);

  printf("Sorted array (descending order): ");
  printArray(arr, n);

  return 0;
}

Here, the key change is in the if condition: if (arr[j] < arr[j + 1]). This ensures that the larger elements “bubble” towards the beginning of the array, resulting in a descending order sort.

Optimized Bubble Sort

Bubble sort can be optimized by stopping the sorting process early if no swaps occur during a pass. This means the array is already sorted.

#include <stdio.h>

void optimizedBubbleSort(int arr[], int n) {
  // `arr` is the array that we want to sort
  // `n` is the number of elements in the array

  // The outer loop goes through each element in the array
  // After each pass, the largest unsorted element is placed at the end
  for (int i = 0; i < n - 1; i++) {

    // Initialize a flag to check if any swaps occurred in this pass
    int swapped = 0;

    // The inner loop compares each adjacent element and swaps them if needed
    for (int j = 0; j < n - i - 1; j++) {

      // Compare the adjacent elements
      // If the first element is larger than the second element then swap
      if (arr[j] > arr[j + 1]) {
        // Swap arr[j] and arr[j+1] using a temporary variable
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = 1;
      }
    }
    // If no two elements were swapped in inner loop, the array is sorted
    if (swapped == 0)
      break;
  }
}

// Utility function to print 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("Original array: ");
  printArray(arr, n);

  optimizedBubbleSort(arr, n);

  printf("Sorted array (optimized): ");
  printArray(arr, n);

  return 0;
}

Explanation of the Optimization:

  • We introduce an integer variable swapped and initialize it to 0 (false) at the beginning of each pass.
  • If a swap occurs in the inner loop, we set swapped = 1 (true).
  • After the inner loop completes, we check if swapped is still 0. If it is, we break out of the outer loop because no swaps were made, indicating the array is already sorted.

Sorting Structures

To sort an array of structures, we need to define how to compare two structures. Let’s consider an example where we sort an array of Student structures based on their age.

#include <stdio.h>
#include <string.h>

// Define the structure for a student
struct Student {
  char name[50];
  int age;
};

// Function to perform bubble sort on an array of Student structures
void bubbleSortStudents(struct Student arr[], int n) {
  // The outer loop goes through each element in the array
  for (int i = 0; i < n - 1; i++) {

    // The inner loop compares each adjacent element and swaps them if needed
    for (int j = 0; j < n - i - 1; j++) {

      // Compare the ages of two students
      if (arr[j].age > arr[j + 1].age) {

        // Swap arr[j] and arr[j+1]
        struct Student temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

int main() {
  struct Student students[] = {
    {"Alice", 20},
    {"Bob", 19},
    {"Charlie", 21}
  };
  int n = sizeof(students) / sizeof(students[0]);

  printf("Original student array:\n");
  for (int i = 0; i < n; i++)
    printf("Name: %s, Age: %d\n", students[i].name, students[i].age);

  bubbleSortStudents(students, n);

  printf("\nSorted student array by age:\n");
  for (int i = 0; i < n; i++)
    printf("Name: %s, Age: %d\n", students[i].name, students[i].age);

  return 0;
}

Key points:

  • We define a Student structure with name and age fields.
  • The bubbleSortStudents function takes an array of Student structures and sorts them based on the age field.
  • The comparison if (arr[j].age > arr[j + 1].age) compares the ages of two students to determine the sorting order.
  • The main function initializes an array of Student structures, calls bubbleSortStudents, and prints the sorted array.

What’s Next?

Now that you’ve learned how to implement bubble sort in C, you might want to explore: