Bubble Sort in C++

Bubble sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. It is a basic sorting technique that is useful in understanding data structure and algorithms. Bubble sort is one of the most common algorithms used in the “Data Structures and Algorithms with C++” course. In this article, we will discuss how bubble sort works, its time complexity, and its space complexity. We will also include C++ code to demonstrate each step of the sorting process. 

How Bubble Sort Works

Bubble sort is a comparison-based algorithm that works by repeatedly stepping through a list and comparing pairs of elements. If the elements are out of order, the algorithm swaps them. The algorithm continues to step through the list and swap elements until the list is sorted. 

To better understand how bubble sort works, let’s consider the following array of integers: [9, 4, 8, 3, 1, 6, 5, 2, 7]. We can use the following C++ code to visualize the algorithm in action: 

// array to be sorted 
int a[] = {9, 4, 8, 3, 1, 6, 5, 2, 7}; 

// size of array 
int n = sizeof(a) / sizeof(a[0]); 

// loop through the entire array 
for (int i = 0; i < n - 1; i++) 
{ 
	// loop through the array elements 
	for (int j = 0; j < n - i - 1; j++) 
	{ 
		// compare adjacent elements 
		if (a[j] > a[j + 1]) 
		{ 
			// swap elements 
			int temp = a[j]; 
			a[j] = a[j + 1]; 
			a[j + 1] = temp; 
		} 
	} 
} 

The above code shows a basic implementation of bubble sort. The outer loop (i) moves from the beginning of the array to the end. The inner loop (j) moves from the beginning of the array to the end of the sorted array. The if statement compares adjacent elements and swaps them if they are out of order. 

At the end of the first iteration (i=0), the largest element (9) is moved to the end of the array. At the end of the second iteration (i=1), the second largest element (8) is moved to the second last position. This process continues until the array is sorted. 

Time Complexity

The time complexity of bubble sort is dependent on the number of elements that need to be sorted. The best case time complexity of bubble sort is O(n), where n is the number of elements in the array. This occurs when the array is already sorted, and the algorithm only needs to make one pass through the array. 

The average case time complexity of bubble sort is O(n2). This occurs when the array is randomly ordered, and the algorithm needs to make multiple passes through the array. 

The worst case time complexity of bubble sort is also O(n2). This occurs when the array is sorted in reverse order, and the algorithm needs to make multiple passes through the array. 

Space Complexity 

The space complexity of bubble sort is O(1), since the algorithm only requires a single additional memory space for swapping elements. 

Conclusion

In this article, we discussed bubble sort, a simple sorting algorithm that works by repeatedly stepping through a list and comparing pairs of elements. We discussed how the algorithm works and its time and space complexity. We also included C++ code to demonstrate each step of the sorting process. 

Exercises

#include <iostream> 

// array to be sorted 
int a[] = {9, 4, 8, 3, 1, 6, 5, 2, 7}; 

// size of array 
int n = sizeof(a) / sizeof(a[0]); 

// function for bubble sorting 
void bubbleSort(int a[], int n) 
{ 
	// loop through the entire array 
	for (int i = 0; i < n - 1; i++) 
	{ 
		// loop through the array elements 
		for (int j = 0; j < n - i - 1; j++) 
		{ 
			// compare adjacent elements 
			if (a[j] > a[j + 1]) 
			{ 
				// swap elements 
				int temp = a[j]; 
				a[j] = a[j + 1]; 
				a[j + 1] = temp; 
			} 
		} 
	} 
} 

// function to print the array 
void printArray(int a[], int n) 
{ 
	for (int i = 0; i < n; i++) 
		std::cout << a[i] << " "; 
	std::cout << std::endl; 
} 

// main function 
int main() 
{ 
	std::cout << "Original array: "; 
	printArray(a, n); 

	bubbleSort(a, n); 

	std::cout << "Sorted array: "; 
	printArray(a, n); 

	return 0; 
} 

#include <iostream> 
#include <string> 

// array to be sorted 
std::string a[] = {"dog", "cat", "bird", "ant", "bee"}; 

// size of array 
int n = sizeof(a) / sizeof(a[0]); 

// function for bubble sorting 
void bubbleSort(std::string a[], int n) 
{ 
	// loop through the entire array 
	for (int i = 0; i < n - 1; i++) 
	{ 
		// loop through the array elements 
		for (int j = 0; j < n - i - 1; j++) 
		{ 
			// compare adjacent elements 
			if (a[j] > a[j + 1]) 
			{ 
				// swap elements 
				std::string temp = a[j]; 
				a[j] = a[j + 1]; 
				a[j + 1] = temp; 
			} 
		} 
	} 
} 

// function to print the array 
void printArray(std::string a[], int n) 
{ 
	for (int i = 0; i < n; i++) 
		std::cout << a[i] << " "; 
	std::cout << std::endl; 
} 

// main function 
int main() 
{ 
	std::cout << "Original array: "; 
	printArray(a, n); 

	bubbleSort(a, n); 

	std::cout << "Sorted array: "; 
	printArray(a, n); 

	return 0; 
}