Bubble Sort in C++

Sorting algorithms play a crucial role in organizing data efficiently. Bubble Sort is a simple and easy-to-implement algorithm. In this article, we will explore Bubble Sort in C++, understanding its working principle, implementation, time complexity, and practical considerations.

• What is Bubble Sort?
• Bubble Sort Algorithm
• How does Bubble Sort work?
• Bubble Sort Implementation in C++
• Time Complexity Analysis
• Advantages of Bubble Sort
• Disadvantages of Bubble Sort
• Bubble Sort Applications
• FAQs

Bubble Sort in C++ is a simple sorting algorithm that repeatedly compares adjacent elements in a list and swaps them if they are in the wrong order. It continues this process until the entire list is sorted.

Here’s the pseudo code for the Bubble Sort algorithm in C++:

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

In the above pseudo code, arr is the input array to be sorted, and n is the length of the array. The algorithm uses nested loops to iterate through the array, comparing adjacent elements and swapping them if they are in the wrong order. This process is repeated until the entire array is sorted.

Here’s an example of Bubble Sort with 5 elements: 6, 4, 2, 8, 3.

Iteration 1:

• Compare 6 and 4: Swap since 4 < 6. List: 4, 6, 2, 8, 3.
• Compare 6 and 2: Swap since 2 < 6. List: 4, 2, 6, 8, 3.
• Compare 6 and 8: No swap since 6 < 8. List: 4, 2, 6, 8, 3.
• Compare 8 and 3: Swap since 3 < 8. List: 4, 2, 6, 3, 8.

Iteration 2:

• Compare 4 and 2: Swap since 2 < 4. List: 2, 4, 6, 3, 8.
• Compare 4 and 6: No swap since 4 < 6. List: 2, 4, 6, 3, 8.
• Compare 6 and 3: Swap since 3 < 6. List: 2, 4, 3, 6, 8.

Iteration 3:

• Compare 2 and 4: No swap since 2 < 4. List: 2, 4, 3, 6, 8.
• Compare 4 and 3: Swap since 3 < 4. List: 2, 3, 4, 6, 8.

Iteration 4:

• Compare 2 and 3: No swap since 2 < 3. List: 2, 3, 4, 6, 8.

The list is now sorted in ascending order. Bubble Sort iterates through the list, comparing adjacent elements and swapping them if necessary, until the entire list is sorted.

This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

/*
 * C++ Program to Implement Bubble Sort
 */
 
#include <iostream>
 
using namespace std;
 
// Sort arr[] of size n using Bubble Sort. 
void BubbleSort (int arr[], int n)
{
    int i, j;
    for (i = 0; i < n; ++i)
    {
        for (j = 0; j < n-i-1; ++j)
        {
            // Comparing consecutive data and switching values if value at j > j+1.
            if (arr[j] > arr[j+1])
            {
                arr[j] = arr[j]+arr[j+1];
                arr[j+1] = arr[j]-arr[j + 1];
                arr[j] = arr[j]-arr[j + 1];
            }
        }
        // Value at n-i-1 will be maximum of all the values below this index.
    }	
}	
 
int main()
{
    int n, i;
    cout<<"\nEnter the number of data element to be sorted: ";
    cin>>n;
 
    int arr[n];
    for(i = 0; i < n; i++)
    {
        cout<<"Enter element "<<i+1<<": ";
        cin>>arr[i];
    }
 
    BubbleSort(arr, n);
 
    // Display the sorted data.
    cout<<"\nSorted Data ";
    for (i = 0; i < n; i++)
    cout<<"->"<<arr[i];
 
    return 0;
}

1. Take input of data.
2. Call BubbleSort() function with ‘arr‘ the array of data and ‘n‘ the number of values, in the argument list.
3. Implement Sorting algorithm using nested for loop.
4. The first loop will run on ‘i‘ from 0 to n-1.
5. The second loop will run on ‘j‘ from 0 to n-i-1.
6. Compare two consecutive values.
7. Switch the values if arr[j+1] <arr[j].
8. Return to main and display the result.
9. Exit.

Testcase 1: (Average Case)

 
Enter the number of data element to be sorted: 5
Enter element 1: 998
Enter element 2: 451
Enter element 3: 2
Enter element 4: 35
Enter element 5: 1206
 
Sorted Data ->2->35->451->998->1206

Testcase 2: (Best Case)

Enter the number of data element to be sorted: 5
Enter element 1: 2
Enter element 2: 332
Enter element 3: 456
Enter element 4: 1024
Enter element 5: 16565
 
Sorted Data ->2->332->456->1024->16565

Testcase 3: (Worst Case)

Enter the number of data element to be sorted: 5
Enter element 1: 99845
Enter element 2: 564
Enter element 3: 332
Enter element 4: 86
Enter element 5: 1
 
Sorted Data ->1->86->332->564->99845

Time Complexity:
In the best case scenario, when the array is already sorted, Bubble Sort has a linear time complexity of O(n). However, in the average and worst case scenarios, where the array is unsorted or in reverse order, Bubble Sort has a quadratic time complexity of O(n²).

Space Complexity:
The space complexity remains constant at O(1) as Bubble Sort only requires a small amount of additional memory for temporary variable storage.

• Easy to understand and implement.
• Requires only a small amount of additional memory.
• Can handle partially sorted or nearly sorted lists efficiently.
• Performs sorting in-place, without requiring extra memory.
• Simple to debug and trace for identifying and fixing issues.

• Bubble Sort may not be the best choice for large datasets, partially sorted lists, or complex sorting tasks.
• It is less efficient compared to other algorithms and lacks stability in certain scenarios.

• Education: Used for teaching sorting algorithms and programming concepts.
• Small datasets: Suitable for sorting small arrays or limited data.
• Testing: Helpful for testing and verifying other sorting algorithms.
• Understanding: Illustrates basic sorting principles like comparisons and swaps.

1. What is Bubble Sort in C++?
Bubble Sort is a simple sorting algorithm in C++ that compares adjacent elements and swaps them if they are out of order, gradually sorting the list.

2. How does Bubble Sort work in C++?
Bubble Sort works by repeatedly comparing and swapping adjacent elements until the list is sorted.

3. What are the advantages of Bubble Sort Algorithm in C++?
Bubble Sort is easy to understand, requires minimal additional memory, and can handle partially sorted lists.

4. What are the disadvantages of Bubble Sort Algorithm in C++?
Bubble Sort is inefficient for large datasets, not suitable for complex sorting tasks, and lacks stability in maintaining the order of equal elements.

5. When should I use Bubble Sort in C++?
Bubble Sort is suitable for small datasets, educational purposes, and simple sorting tasks. For larger datasets or time-critical applications, other sorting algorithms are more efficient.

To practice programs on every topic in C++, please visit “Programming Examples in C++”, “Data Structures in C++” and “Algorithms in C++”.