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++.<\/p>\n
Write a program to sort a given integer array in ascending order.<\/p>\n
\nThe input is an array consisting of multiple integers. For example, let's assume the following array is given:\n[64, 34, 25, 12, 22, 11, 90]\n<\/pre>\nOutput<\/h3>\n
\nOutput the result of the array sorted in ascending order. For example, the output for the above input would be:\n[11, 12, 22, 25, 34, 64, 90]\n<\/pre>\nBubble Sort Algorithm<\/h2>\n
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:<\/p>\n
\n
- Start from the first element of the array and compare two adjacent elements.<\/li>\n
- If the first element is larger than the second element, swap the two elements.<\/li>\n
- Repeat this process until the end of the array.<\/li>\n
- Repeat this process for the length of the array – 1, so that if a sorted section is created, you can terminate the loop early.<\/li>\n<\/ol>\n
C++ Code Implementation<\/h2>\n
Now, let’s implement Bubble Sort using C++. Below is the C++ code that implements Bubble Sort:<\/p>\n
\n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nvoid bubbleSort(vector<int>& arr) {\n int n = arr.size();\n bool swapped;\n \n \/\/ Iterate through all elements of the array\n for (int i = 0; i < n - 1; i++) {\n swapped = false;\n \/\/ The last i elements are already sorted, so iterate until n-i-1\n for (int j = 0; j < n - i - 1; j++) {\n if (arr[j] > arr[j + 1]) {\n \/\/ Swap the two elements\n swap(arr[j], arr[j + 1]);\n swapped = true;\n }\n }\n \/\/ If no elements were swapped, the array is already sorted, so we exit\n if (!swapped) break;\n }\n}\n\nint main() {\n vector<int> data = {64, 34, 25, 12, 22, 11, 90};\n \n cout << \"Array before sorting: \";\n for (int num : data) {\n cout << num << \" \";\n }\n \n bubbleSort(data);\n \n cout << \"\\nArray after sorting: \";\n for (int num : data) {\n cout << num << \" \";\n }\n \n return 0;\n}\n<\/code><\/pre>\nCode Explanation<\/h3>\n
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<\/code> library. ThebubbleSort<\/code> function performs the sorting operation on the passed array.<\/p>\n\n
int n = arr.size();<\/code> – Gets the size of the array.<\/li>\nfor (int i = 0; i < n - 1; i++)<\/code> – Iterates through all elements of the array.<\/li>\nfor (int j = 0; j < n - i - 1; j++)<\/code> – Compares within the range of the last i sorted elements.<\/li>\nif (arr[j] > arr[j + 1])<\/code> – If the two elements are not in order, uses theswap<\/code> function to exchange them.<\/li>\nif (!swapped) break;<\/code> – If no swaps occurred, the array is already sorted, so it exits the loop early.<\/li>\n<\/ul>\nTesting and Result Verification<\/h2>\n
Now, let’s execute the code to check the results. The output when the above code is executed is as follows:<\/p>\n
\nArray before sorting: 64 34 25 12 22 11 90 \nArray after sorting: 11 12 22 25 34 64 90 \n<\/code><\/pre>\nAlgorithm Analysis<\/h2>\n
Bubble Sort is easy to understand, but it has issues with efficiency. The time complexity in the worst and average cases is O(n\u00b2). 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.<\/p>\n
Time Complexity<\/h3>\n
\n
- Worst case: O(n\u00b2)<\/li>\n
- Average case: O(n\u00b2)<\/li>\n
- Best case: O(n) (when already sorted)<\/li>\n<\/ul>\n
Space Complexity<\/h3>\n
\n
- O(1) (as it directly modifies the given array)<\/li>\n<\/ul>\n
Pros and Cons of Bubble Sort<\/h2>\n
Pros<\/h3>\n