C++ Coding Test Course, Bubble Sort

1. Problem Description

Bubble Sort is one of the simplest sorting algorithms that sorts by comparing two adjacent elements. The characteristic of this algorithm is that it is intuitive and easy to implement. However, it tends to be slower compared to other sorting algorithms in terms of efficiency.

Problem

Sort the given integer array in ascending order using Bubble Sort.

Input Example:
[64, 34, 25, 12, 22, 11, 90]

Output Example:
[11, 12, 22, 25, 34, 64, 90]

2. Problem Analysis

The core idea of Bubble Sort is to sort by comparing adjacent elements. Starting from the first element of the array, elements are compared two at a time, repeatedly sending larger values to the back. This process is repeated several times until the entire array is sorted.

How Bubble Sort Works

For instance, let’s look at the process of applying Bubble Sort to the array [64, 34, 25, 12, 22, 11, 90]:

First Iteration:
- Compare 64 and 34 → [34, 64, 25, 12, 22, 11, 90]
- Compare 64 and 25 → [34, 25, 64, 12, 22, 11, 90]
- Compare 64 and 12 → [34, 25, 12, 64, 22, 11, 90]
- Compare 64 and 22 → [34, 25, 12, 22, 64, 11, 90]
- Compare 64 and 11 → [34, 25, 12, 22, 11, 64, 90]
- Compare 64 and 90 → [34, 25, 12, 22, 11, 64, 90] (no change)
Second Iteration: (The largest number has moved to the back, so the last element is not compared)
- Compare 34 and 25 → [25, 34, 12, 22, 11, 64, 90]
- Compare 34 and 12 → [25, 12, 34, 22, 11, 64, 90]
- Compare 34 and 22 → [25, 12, 22, 34, 11, 64, 90]
- Compare 34 and 11 → [25, 12, 22, 11, 34, 64, 90]
- Compare 34 and 64 → [25, 12, 22, 11, 34, 64, 90] (no change)
(Repeating this process ultimately yields the sorted array.)

3. Time Complexity

The time complexity of Bubble Sort is O(n^2) in the worst case. This occurs because all pairs need to be compared when the size of the array is n. It has a performance of O(n^2) in the average case, while in the best case (when the array is already sorted), it is O(n).

4. Code Implementation

Below is the Bubble Sort code implemented in C++:

#include <iostream>
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]);

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

    return 0;
}

5. Code Explanation

#include <iostream>: Includes the C++ standard input-output library.
void bubbleSort(int arr[], int n): A function that takes the array to be sorted and the size of the array as parameters.
Uses a nested for loop to compare the elements of the array and performs a swap when necessary. The inner loop compares arr[j] and arr[j+1] to send the larger value backward.
int main(): The entry point of the program, initializes the array to be sorted, and calls the bubbleSort function to sort it.
Prints the sorted array.

6. Performance Analysis

Bubble Sort has the advantage of being easy to implement, but it is inefficient for large scales of data. In practice, it is not often used, but it can serve as a good example for enhancing understanding while learning data structures and algorithms.

7. Conclusion

In this lecture, we explored the concept of Bubble Sort and its implementation in C++. When solving algorithm problems, it is important not only to solve the problem but also to consider various optimization techniques in the process. In the next lecture, we will look at more efficient sorting algorithms, such as Quick Sort or Merge Sort. Thank you!