C++ Coding Test Course, Bubble Sort Program 1

In this course, we will cover how to implement the Bubble Sort algorithm using C++. Bubble Sort is one of the simplest sorting algorithms, which sorts by comparing two adjacent elements and moving the larger element backward. This algorithm will help you understand the basics of sorting algorithms and learn how to implement it in C++.

Problem Definition

Write a program to sort a given integer array in ascending order.

Input

The input is an array consisting of multiple integers. For example, let's assume the following array is given:
[64, 34, 25, 12, 22, 11, 90]

Output

Output the result of the array sorted in ascending order. For example, the output for the above input would be:
[11, 12, 22, 25, 34, 64, 90]

Bubble Sort Algorithm

The basic idea of Bubble Sort is to compare two adjacent elements to sort them. If the first element is larger than the second element, the two elements are swapped. This process is repeated until the end of the array, and at the end of each iteration, the largest element moves to the last position. Below are simple steps to explain the Bubble Sort algorithm:

  1. Start from the first element of the array and compare two adjacent elements.
  2. If the first element is larger than the second element, swap the two elements.
  3. Repeat this process until the end of the array.
  4. Repeat this process for the length of the array – 1, so that if a sorted section is created, you can terminate the loop early.

C++ Code Implementation

Now, let’s implement Bubble Sort using C++. Below is the C++ code that implements Bubble Sort:

 
#include <iostream>
#include <vector>

using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    
    // Iterate through all elements of the array
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        // The last i elements are already sorted, so iterate until n-i-1
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap the two elements
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // If no elements were swapped, the array is already sorted, so we exit
        if (!swapped) break;
    }
}

int main() {
    vector<int> data = {64, 34, 25, 12, 22, 11, 90};
    
    cout << "Array before sorting: ";
    for (int num : data) {
        cout << num << " ";
    }
    
    bubbleSort(data);
    
    cout << "\nArray after sorting: ";
    for (int num : data) {
        cout << num << " ";
    }
    
    return 0;
}

Code Explanation

The above code is a simple example of how to implement Bubble Sort in C++. First, we declare and initialize an integer array using the vector library. The bubbleSort function performs the sorting operation on the passed array.

  • int n = arr.size(); – Gets the size of the array.
  • for (int i = 0; i < n - 1; i++) – Iterates through all elements of the array.
  • for (int j = 0; j < n - i - 1; j++) – Compares within the range of the last i sorted elements.
  • if (arr[j] > arr[j + 1]) – If the two elements are not in order, uses the swap function to exchange them.
  • if (!swapped) break; – If no swaps occurred, the array is already sorted, so it exits the loop early.

Testing and Result Verification

Now, let’s execute the code to check the results. The output when the above code is executed is as follows:


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

Algorithm Analysis

Bubble Sort is easy to understand, but it has issues with efficiency. The time complexity in the worst and average cases is O(n²). This means that performance significantly degrades as the size of the array increases. For this reason, Bubble Sort is more suitable for educational purposes than for practical applications.

Time Complexity

  • Worst case: O(n²)
  • Average case: O(n²)
  • Best case: O(n) (when already sorted)

Space Complexity

  • O(1) (as it directly modifies the given array)

Pros and Cons of Bubble Sort

Pros

  • The algorithm is simple.
  • It is easy for beginners to understand.
  • It can identify whether it is already sorted on its own.

Cons

  • High time complexity makes it inefficient for real applications.
  • Not recommended for large datasets.

Conclusion

In this course, we learned how to implement sorting algorithms in C++ through Bubble Sort. We gained an understanding of the basic concepts of Bubble Sort and its algorithm implementation. In the future, I encourage you to study more efficient sorting algorithms (e.g., Quick Sort, Merge Sort, etc.) in depth.

I hope this article was helpful for your C++ coding test preparation. If you have any further questions or would like to learn about more algorithms, please leave a comment!