Bubble Sort Algorithm Code In C++

5 min read Jul 01, 2024

Bubble Sort Algorithm Code in C++

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Algorithm Description

Start with the first element.
Compare the current element with the next element.
If the current element is greater than the next element, swap them.
Move to the next element and repeat steps 2-3.
Repeat steps 1-4 for the entire list.
If no swaps were made in a pass, the list is sorted.

C++ Code Implementation

#include 

using namespace std;

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

// Function to print an array
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

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

  cout << "Original array: ";
  printArray(arr, n);

  bubbleSort(arr, n);

  cout << "Sorted array: ";
  printArray(arr, n);

  return 0;
}

Explanation

bubbleSort(int arr[], int n) function: This function implements the bubble sort algorithm.
- Outer loop: It iterates through the array from the beginning to the second last element.
- Inner loop: It compares adjacent elements and swaps them if they are in the wrong order.
- swapped flag: It indicates whether any swaps were made in a pass. If no swaps were made, the list is sorted, and the loop breaks.
printArray(int arr[], int size) function: This function prints the array.
main() function:
- Initializes an unsorted array.
- Calls bubbleSort() to sort the array.
- Calls printArray() to print the original and sorted arrays.

Time and Space Complexity

Time Complexity: Bubble Sort has a time complexity of O(n^2) in the worst and average cases, and O(n) in the best case when the array is already sorted.
Space Complexity: Bubble Sort has a space complexity of O(1) as it only uses a constant amount of extra space for swapping elements.

Advantages

Simple to implement: Bubble sort is a simple and easy-to-understand algorithm.
In-place sorting: It sorts the array in place without requiring extra memory.

Disadvantages

Inefficient for large arrays: Bubble sort is inefficient for large arrays as it has a quadratic time complexity.
Not stable: Bubble sort is not a stable sorting algorithm, meaning that the relative order of elements with the same value may change.

Conclusion

Bubble sort is a simple sorting algorithm that is easy to understand and implement, but it is not efficient for large arrays. It is best used for small datasets or as a starting point for understanding more complex sorting algorithms.

Bubble Sort Algorithm Code In C++