C++ Coding Test Course, Bubble Sort Program 2

Hello! In this tutorial, we will learn how to implement the Bubble Sort algorithm using C++. Bubble Sort is a simple and easy-to-understand sorting algorithm, mainly used for educational purposes. In this article, we will explain the basic concepts of Bubble Sort, its time complexity, and the actual implementation step by step.

Overview of Bubble Sort Algorithm

Bubble Sort is a method that sorts by comparing two adjacent elements. This process is repeated until all elements of the list are sorted. The name Bubble Sort comes from the way the largest value ‘bubbles’ up to the back.

How Bubble Sort Works

  1. Compare the first element of the list with the second element.
  2. If the first element is greater than the second element, swap their positions.
  3. Repeat this process all the way to the end of the list. One cycle of this process is called a ‘pass’.
  4. Repeat steps 1 to 3 until the sorting is complete.

Time Complexity

The time complexity of Bubble Sort is O(n^2) in the worst case. This is because each element of the list needs to be compared once. The best case (when already sorted) is also O(n). For this reason, Bubble Sort is inefficient for sorting large datasets.

Algorithm Implementation

Now, let’s implement Bubble Sort through C++ code. First, we’ll take a look at the basic Bubble Sort code and explain each part.

#include <iostream>
using namespace std;

// Bubble Sort function
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            // Swap positions if the current element is greater than the next element
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

// Array printing function
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Main function
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Array before sorting: ";
    printArray(arr, n);
    
    bubbleSort(arr, n);
    
    cout << "Array after sorting: ";
    printArray(arr, n);
    return 0;
}

Code Explanation

  • #include <iostream>: This is the header file for standard input and output.
  • swap(arr[j], arr[j + 1]): This uses C++’s built-in function swap to exchange the current element with the next one.
  • printArray function: This is a function to print the given array.
  • main function: This is the starting point of the program, where array initialization and sorting calls take place.

Execution Result

Running the above code produces the following results:

Array before sorting: 64 34 25 12 22 11 90 
Array after sorting: 11 12 22 25 34 64 90

By comparing the array before and after sorting, we can confirm that Bubble Sort is functioning correctly.

Ways to Improve Bubble Sort

The basic Bubble Sort implementation includes unnecessary comparisons. If no swaps occur during a pass, it indicates that the list is already sorted, and no additional passes are needed. This can enhance the efficiency of the algorithm.

void improvedBubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true; // Record that a swap occurred
            }
        }
        if (!swapped) break; // Exit loop if no more swaps
    }
}

Conclusion

In this tutorial, we learned how to implement Bubble Sort using C++. Although it is a simple algorithm, it is less efficient in practice, requiring more efficient algorithms. However, Bubble Sort is worth mentioning due to its educational value.

We will continue to provide C++ algorithm tutorials, so please stay tuned! If you have any questions or comments, please leave them in the comments!