C++ Bubble Sort Array Example

MUAZHAN

5 min read

·

Jul 01, 2024

29

Share

C++ Bubble Sort Array Example

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.

Here's a C++ example of implementing bubble sort on an array:

#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] and arr[j+1]
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

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

  cout << "Unsorted array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;

  bubbleSort(arr, n);

  cout << "Sorted array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;

  return 0;
}

Explanation:

1. bubbleSort(int arr[], int n): This function implements the bubble sort algorithm.
   • for (int i = 0; i < n - 1; i++): This outer loop iterates through the array n - 1 times.
   • for (int j = 0; j < n - i - 1; j++): This inner loop compares adjacent elements and swaps them if necessary. The number of comparisons in each pass decreases as the loop progresses because the largest elements are already bubbled up to the end.
   • if (arr[j] > arr[j + 1]): This condition checks if the element at index j is greater than the element at index j + 1. If true, a swap is performed.
   • Swap using a temporary variable: The temp variable is used to temporarily store the value of arr[j] before the swap.
2. main() function:
   • Declare an array arr and its size n: Initializes an array of integers and calculates its size.
   • Print the unsorted array: Displays the elements of the array before sorting.
   • Call bubbleSort(arr, n): Sorts the array using the bubble sort function.
   • Print the sorted array: Displays the elements of the array after sorting.

Output:

Unsorted array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90 

Key points about bubble sort:

• Time Complexity: Bubble sort has a time complexity of O(n^2) in the worst and average cases. This means that the number of operations increases quadratically with the size of the input.
• Space Complexity: Bubble sort has a space complexity of O(1) because it only requires a constant amount of extra space for the temporary variable used during the swap operation.
• In-Place Sorting: Bubble sort is an in-place sorting algorithm because it modifies the original array directly without creating a new copy.
• Stability: Bubble sort is a stable sorting algorithm, meaning that elements with equal values maintain their relative order in the sorted output.

While bubble sort is simple to understand and implement, it is generally not the most efficient sorting algorithm for large datasets. For practical applications, more efficient algorithms like merge sort or quicksort are usually preferred.