Introduction:
In this blog post, we'll explore the Bubble Sort algorithm, a simple sorting technique that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the entire list is sorted. We'll discuss the algorithm's basic steps, its implementation, and provide a breakdown of the code.
The Challenge:
The task is to implement the Bubble Sort algorithm to sort an array of distinct elements in ascending order. After sorting, we need to print the following information:
The number of swaps that took place during the sorting process.
The first element in the sorted array.
The last element in the sorted array.
Format & Sample:
Input Format:
The input consists of two lines:
The first line contains an integer, n, representing the number of elements in the array.
The second line contains n space-separated integers representing the elements of the array.
Output Format:
Print the following three lines of output:
"Array is sorted in numSwaps swaps," where numSwaps is the number of swaps that took place.
"First Element: firstElement," where firstElement is the first element in the sorted array.
"Last Element: lastElement," where lastElement is the last element in the sorted array.
Sample Input:
3
1 2 3
Sample Output:
Array is sorted in 0 swaps.
First Element: 1
Last Element: 3
Explanation:
The array is already sorted, so no swaps take place, and we print the necessary lines of output.
Code Breakdown:
Now, let's break down the provided C++ code.
Reading Input:
string n_temp;
getline(cin, n_temp);
int n = stoi(ltrim(rtrim(n_temp)));
string a_temp_temp;
getline(cin, a_temp_temp);
vector<string> a_temp = split(rtrim(a_temp_temp));
vector<int> a(n);
for (int i = 0; i < n; i++) {
int a_item = stoi(a_temp[i]);
a[i] = a_item;
}
The code reads the number of elements n and the array elements a from the standard input.
Sorting with Bubble Sort:
for (int i = 0; i < n; i++) {
int noOfSwaps = 0;
for (int j = 0; j < n - 1; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
noOfSwaps++;
}
}
if (noOfSwaps == 0) {
break;
}
}
This part of the code implements the Bubble Sort algorithm. It counts the number of swaps and prints the required output after each pass. The process continues until the array is sorted.
Utility Functions:
string ltrim(const string &str) { /* ... */ }
string rtrim(const string &str) { /* ... */ }
vector<string> split(const string &str) { /* ... */ }
These functions are utility functions for trimming and splitting strings, ensuring proper input handling.
Final Code:
#include <iostream>
#include <vector>
using namespace std;
string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);
int main()
{
// Read the number of elements
string n_temp;
getline(cin, n_temp);
int n = stoi(ltrim(rtrim(n_temp)));
// Read the array elements
string a_temp_temp;
getline(cin, a_temp_temp);
vector<string> a_temp = split(rtrim(a_temp_temp));
// Convert string array to integer array
vector<int> a(n);
for (int i = 0; i < n; i++) {
int a_item = stoi(a_temp[i]);
a[i] = a_item;
}
// Bubble Sort Algorithm
int totalSwaps = 0;
for (int i = 0; i < n; i++) {
int numberOfSwaps = 0;
for (int j = 0; j < n - 1; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
numberOfSwaps++;
}
}
totalSwaps += numberOfSwaps;
// If no swaps occurred, the array is sorted, and we can exit
if (numberOfSwaps == 0) {
break;
}
}
// Print the output
cout << "Array is sorted in " << totalSwaps << " swaps." << endl;
cout << "First Element: " << a[0] << endl;
cout << "Last Element: " << a[n - 1] << endl;
return 0;
}
string ltrim(const string &str)
{
string s(str);
s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);
return s;
}
string rtrim(const string &str)
{
string s(str);
s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
s.end()
);
return s;
}
vector<string> split(const string &str)
{
vector<string> tokens;
string::size_type start = 0;
string::size_type end = 0;
while ((end = str.find(" ", start)) != string::npos) {
tokens.push_back(str.substr(start, end - start));
start = end + 1;
}
tokens.push_back(str.substr(start));
return tokens;
}
Conclusion:
Bubble Sort is a straightforward sorting algorithm suitable for small datasets. While it may not be the most efficient for large datasets, understanding its principles contributes to a solid foundation in sorting algorithms.