Bubble Sort Descending Order C++

5 min read Jul 05, 2024

Bubble Sort Descending Order 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. This process is repeated until the list is sorted. This article will guide you through implementing bubble sort in C++ for sorting a list in descending order.

Understanding the Algorithm

The basic idea of bubble sort in descending order is:

Iteration: Start from the beginning of the list.
Comparison: Compare each pair of adjacent elements.
Swap: If the first element is smaller than the second, swap them.
Repeat: Repeat steps 2 and 3 for the entire list.
Continue: Repeat steps 1 to 4 until no swaps are performed in a complete iteration.

C++ Implementation

Here's a C++ implementation of bubble sort for descending order:

#include 

using namespace std;

// Function to perform bubble sort in descending order
void bubbleSortDescending(int arr[], int n) {
  bool swapped;
  for (int i = 0; i < n - 1; i++) {
    swapped = false;
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] < arr[j + 1]) {
        // Swap elements if they are in the wrong order
        swap(arr[j], arr[j + 1]);
        swapped = true;
      }
    }
    // If no swaps occurred in a complete iteration, the array is sorted
    if (!swapped)
      break;
  }
}

int main() {
  int arr[] = {5, 2, 9, 1, 7};
  int n = sizeof(arr) / sizeof(arr[0]);

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

  bubbleSortDescending(arr, n);

  cout << "\nSorted array in descending order: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;

  return 0;
}

Explanation:

bubbleSortDescending(int arr[], int n): This function takes an integer array arr and its size n as input and sorts it in descending order.
swapped variable: A boolean variable to track if any swaps happened during an iteration. If no swaps occur, the array is sorted.
Outer loop: Iterates through the array from the beginning until the second last element (n-1).
Inner loop: Iterates through the array, comparing adjacent elements and swapping them if necessary.
swap(arr[j], arr[j + 1]): Swaps the two adjacent elements using the swap function.
if (!swapped): If no swaps occurred in the inner loop, the array is sorted, and we break out of the outer loop.

Advantages and Disadvantages

Advantages:

Simple to implement: The algorithm is easy to understand and implement.
In-place sorting: It sorts the array without requiring additional memory.

Disadvantages:

Time Complexity: It has a time complexity of O(n^2), making it inefficient for large arrays.
Not suitable for large datasets: Due to its quadratic time complexity, bubble sort is not recommended for large datasets.

Conclusion

While bubble sort is a simple sorting algorithm, it's not the most efficient choice for large datasets. For more complex applications, consider using more efficient algorithms like merge sort or quicksort. However, it serves as a good starting point for understanding basic sorting concepts.