Bubble Sort Algorithm In C++ Data Structure

5 min read Jul 01, 2024

Bubble Sort Algorithm in C++ Data Structure

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 the list is sorted.

Understanding the Algorithm

Iteration: The algorithm iterates through the list multiple times.
Comparison: In each iteration, adjacent elements are compared.
Swapping: If the elements are in the wrong order (i.e., the left element is larger than the right element), they are swapped.
Sorting: After each iteration, the largest element "bubbles up" to its correct position at the end of the list. The process continues, sorting the remaining elements.

C++ Implementation

#include 

using namespace std;

void bubbleSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
      }
    }
  }
}

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 << "Unsorted array: ";
  printArray(arr, n);

  bubbleSort(arr, n);

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

  return 0;
}

Explanation

bubbleSort(int arr[], int n): This function takes an integer array arr and its size n as input.
Nested Loops: The outer loop iterates n-1 times, ensuring each element gets compared with its neighbor at least once. The inner loop iterates through the unsorted portion of the array.
Comparison and Swapping: Inside the inner loop, arr[j] is compared with arr[j + 1]. If arr[j] is larger, they are swapped using the swap() function.
printArray(int arr[], int size): This function prints the elements of the array.
main(): In the main() function, an unsorted array is created, sorted using bubbleSort(), and then printed.

Time Complexity

Bubble Sort has a time complexity of O(n^2) in the worst and average case, where 'n' is the number of elements in the array. This means that the time taken to sort the array increases quadratically with the number of elements.

Advantages

Easy to understand and implement: Bubble Sort is a simple algorithm that is easy to grasp and code.
In-place sorting: It sorts the array without requiring any additional memory.

Disadvantages

Inefficient for large datasets: Its time complexity makes it unsuitable for large datasets.
Slow performance: It performs poorly compared to more efficient sorting algorithms like Merge Sort or Quick Sort.

Conclusion

Bubble Sort is a basic sorting algorithm that can be helpful for understanding sorting concepts. However, due to its inefficiencies, it is not recommended for practical use in most scenarios. More efficient sorting algorithms are available for handling larger datasets.

Bubble Sort Algorithm In C++ Data Structure