Quartz 4

How to sort an array in C++ for beginners ➡️

6 min read

Metadata

  • 📅 Date :: 09-06-2025
  • 🏷️ Tags :: cpp

Notes

Detailed Notes on Sorting an Array Using Bubble Sort in C++

In this tutorial, we will be learning how to sort an array in C++ using the Bubble Sort algorithm. Bubble Sort is one of the simplest sorting algorithms to implement and understand, though it’s not the most efficient for larger datasets. Despite that, it’s a great starting point for beginners to understand sorting principles.

Key Concepts

  1. Sorting: Sorting refers to arranging elements in a particular order—either in ascending or descending order.
  2. Bubble Sort Algorithm: It is a comparison-based sorting algorithm where adjacent elements are compared and swapped if they are in the wrong order. This process repeats until no more swaps are needed, which indicates the array is sorted.

Step-by-Step Explanation

1. Understanding the Bubble Sort Logic

The basic logic behind Bubble Sort is as follows:

  • Start at the beginning of the array (index 0).
  • Compare each adjacent pair of elements: If the element on the left is larger than the element on the right, swap them.
  • Repeat this process: Once you finish comparing and swapping (if necessary) for one pair, move to the next pair and continue until the end of the array.
  • Continue with the next pass: After the first pass, the largest element will be “bubbled up” to the end of the array, so in subsequent passes, you don’t need to check the last elements again.
  • Finish when no more swaps are needed: If during a pass no swaps are made, the array is already sorted, and the process terminates early.

2. Bubble Sort Visualized

Let’s walk through an example to clarify the logic:

Consider the array:

[9, 7, 5, 3, 1]

  • First pass:
    • Compare 9 and 7 → Swap them → [7, 9, 5, 3, 1]
    • Compare 9 and 5 → Swap them → [7, 5, 9, 3, 1]
    • Compare 9 and 3 → Swap them → [7, 5, 3, 9, 1]
    • Compare 9 and 1 → Swap them → [7, 5, 3, 1, 9] (9 is now at the end)
  • Second pass:
    • Compare 7 and 5 → Swap them → [5, 7, 3, 1, 9]
    • Compare 7 and 3 → Swap them → [5, 3, 7, 1, 9]
    • Compare 7 and 1 → Swap them → [5, 3, 1, 7, 9] (7 is now in the second-to-last position)
  • Continue this process until the entire array is sorted.

Step-by-Step Code Implementation

  1. Define the Array and Calculate Size

    First, create an array with integers and calculate its size:

int numbers[] = {9, 7, 5, 3, 1};
int size = sizeof(numbers) / sizeof(numbers[0]);

Here, numbers is the array, and size holds the number of elements in the array.

  1. Display the Unsorted Array

    Before sorting, display the original unsorted array:

for (int element : numbers) {
    cout << element << " ";
}
cout << endl;

  1. Create the Sort Function

    Define the sort function to sort the array using Bubble Sort. The function takes two parameters: the array and its size.

void sort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {  // Loop for each pass
        for (int j = 0; j < size - i - 1; j++) {  // Nested loop for comparing adjacent elements
            if (arr[j] > arr[j + 1]) {  // Compare and swap if necessary
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
  • The outer loop (for (int i = 0; i < size - 1; i++)) represents the number of passes over the array.
  • The inner loop (for (int j = 0; j < size - i - 1; j++)) compares adjacent elements and swaps them if necessary.
  • The condition arr[j] > arr[j + 1] checks if the current element is greater than the next one.
  • Swapping: Use a temporary variable temp to swap the elements.

  1. Call the Sort Function

    Call the sort function before printing the sorted array:

sort(numbers, size);

  1. Display the Sorted Array

    After sorting, display the array:

for (int element : numbers) {
    cout << element << " ";
}
cout << endl;

Sorting in Descending Order

To sort the array in descending order, modify the comparison condition inside the if statement:

if (arr[j] < arr[j + 1]) {  // Swap if the current element is smaller than the next

With this change, the array will be sorted in descending order, as the larger elements will “bubble” to the front.

Final Code

Here’s the full code implementing Bubble Sort:

#include <iostream>
using namespace std;
 
void sort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {  // Outer loop
        for (int j = 0; j < size - i - 1; j++) {  // Inner loop
            if (arr[j] > arr[j + 1]) {  // If the current element is greater than the next
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;  // Swap the elements
            }
        }
    }
}
 
int main() {
    int numbers[] = {9, 7, 5, 3, 1};
    int size = sizeof(numbers) / sizeof(numbers[0]);
 
    cout << "Original array: ";
    for (int element : numbers) {
        cout << element << " ";
    }
    cout << endl;
 
    sort(numbers, size);
 
    cout << "Sorted array: ";
    for (int element : numbers) {
        cout << element << " ";
    }
    cout << endl;
 
    return 0;
}

Output:

Original array: 9 7 5 3 1
Sorted array: 1 3 5 7 9

Efficiency and Time Complexity

  • Time Complexity:
    • The worst-case and average time complexity of Bubble Sort is O(n^2), where n is the number of elements in the array. This happens because for each pass over the array, the algorithm checks all the elements.
    • The best-case time complexity is O(n), which occurs if the array is already sorted. In this case, Bubble Sort can terminate early if no swaps are made during a pass.
  • Space Complexity:
    • Bubble Sort is an in-place sorting algorithm, meaning it does not require extra space beyond the array being sorted. Hence, its space complexity is O(1).

Conclusion

Bubble Sort is a simple and intuitive sorting algorithm that swaps adjacent elements if they are in the wrong order. While it is easy to implement and understand, it is not efficient for large datasets due to its quadratic time complexity. For smaller arrays or as an educational tool, Bubble Sort is a useful starting point. However, for large datasets, more efficient algorithms like Quick Sort or Merge Sort should be used.

References

Graph View

Backlinks