Sorting Algorithms: Bubble Sort
Bubble Sort is a simple sorting algorithm for sorting a given collection of n elements in an array with n elements. Bubble Sort compares each element one by one and sorts them based on their values.
If the given array must be sorted in ascending order, bubble sort will begin by comparing the first and second elements of the array; if the first element is greater than the second element, it will swap both elements and then move on to compare the second and third elements, and so on.
If we have n elements, we must repeat the operation n-1 times. It is called bubble sort because the most significant element in the given array bubbles up to the last place or the highest index with each complete iteration, much like a water bubble rises to the water's surface.
Sorting is accomplished by going through each element individually, comparing it to the neighboring element, and swapping them if necessary.
Note: If you are unfamiliar with Sorting in the data structure, you should first learn what sorting is to understand the fundamentals of sorting.
Basics of Sorting Algorithms
A sorting algorithm is a step-by-step technique for arranging elements in a particular order. It accepts an unordered list of elements and rearranges them in the appropriate order, such as ascending or descending.
Sorting algorithms work by comparing elements in a list and rearranging them until they are in the correct order. This process of comparison and rearranging continues until the complete list is sorted.
Sorting algorithms are categorized based on time complexity, stability, and space complexity. The amount of time it takes an algorithm to run is called its temporal complexity, often defined as the number of comparisons or operations completed.
The algorithm's stability relates to whether it preserves the relative order of elements with equal values. The amount of extra memory the algorithm utilizes is called its space complexity.
Bubble Sort Working
Assume we want to arrange the components in ascending order.
The Initial Iteration (Compare and Swap)
Step 1: Compare the first and second elements starting with the first index.
Step 2: They are exchanged if the first element is more significant than the second.
Step 3: Compare the second and third items now. If they need to be in the correct order, swap them.
Step 4: The above procedure is repeated until the final element is reached.
The Next Iteration/Remaining Iteration
Step 1: The technique is repeated for the remaining iterations.
Step 2: After each iteration, the most significant element among the unsorted items is placed.
The comparison is performed up to the final unsorted element in each iteration.
The array is sorted when all of the unsorted elements are placed in their correct placements.
Bubble Sort Algorithm
This algorithm includes
From the left, compare adjacent items, and the higher one is placed on the right side.
In this manner, the most incredible piece is initially relocated to the rightmost end.
This process is repeated to discover the next largest, place it, and so on until all the data is sorted.
Now, let us have a look at the bubble sort algorithm.
bubbleSort(array) for i <- 1 to indexOfLastUnsortedElement-1 if leftElement > rightElement swap leftElement and rightElementend bubbleSort
Bubble Sort Algorithm Implementation
In the following section of the article, we will look at implementing the Bubble sort algorithm in C, C++, and Java programming languages. Let us have a look at all of them.
C Code:
// Bubble sort algorithm in C #include <stdio.h> //Perform the bubble sortvoid bubbleSort(int array[], int size) { // loop to access each array element for (int step = 0; step < size - 1; ++step) { // loop to compare array elements for (int i = 0; i < size - step - 1; ++i) { //Compare two adjacent elements // change > to < to sort in descending order if (array[i] > array[i + 1]) { // swapping occurs if elements // are not in the intended order int temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; } } }} // print arrayvoid printArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("\n");} int main() { int data[] = {-5, 42, 6, 10, -1}; //Find the array's length int size = sizeof(data) / sizeof(data[0]); bubbleSort(data, size); printf("Sorted Array in Ascending Order is as follows:\n"); printArray(data, size);}
Output:
The sorted Array in Ascending Order is as follows:
-5 -1 6
10 42
C++ Code:
// Bubble sort algorithm in C++ #include <iostream>using namespace std; //Perform bubble sortvoid bubbleSort(int array[], int size) { // loop to access each array element for (int step = 0; step < size; ++step) { // loop to compare array elements for (int i = 0; i < size - step; ++i) { //Compare two adjacent elements // change > to < to sort in descending order if (array[i] > array[i + 1]) { // swapping elements of elements // are not in the intended order int temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; } } }} // print arrayvoid printArray(int array[], int size) { for (int i = 0; i < size; ++i) { cout << " " << array[i]; } cout << "\n";} int main() { int data[] = {-8, 32, 5, 19, -99}; //Find the array's length int size = sizeof(data) / sizeof(data[0]); bubbleSort(data, size); cout << "Sorted Array in Ascending Order is as follows:\n"; printArray(data, size);}
Output:
The sorted Array in Ascending Order is as follows:
-99 -8 0
5 19
Java Code:
// Bubble sort algorithm in Java import java.util.Arrays; class Main { // perform the bubble sort static void bubbleSort(int array[]) { int size = array.length; // loop to access each array element for (int i = 0; i < size - 1; i++) // loop to compare array elements for (int j = 0; j < size - i - 1; j++) // compare two adjacent elements // change > to < to sort in descending order if (array[j] > array[j + 1]) { // swapping occurs if elements // are not in the intended order int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } public static void main(String args[]) { int[] data = { -22, 81, 5, 17, -5 }; // call method using class name Main.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); }}
Output:
Sorted Array in Ascending Order:
[-22, -5, 5, 17, 81]
About Optimized Bubble Sort Algorithm
The above technique does all comparisons even if the array is already sorted.
This lengthens the execution time.
To address this, we can introduce a swapped variable. If elements are exchanged, the value of the swap is set to true. If not, it is set to false.
The swapped value will be false if no swapping occurs after an iteration. This signifies that the elements have already been sorted and that no additional iterations are required.
This reduces execution time and aids in the optimization of the bubble sort. The optimized bubble sort algorithm is
bubbleSort(array) swapped <- false for i <- 1 to indexOfLastUnsortedElement-1if leftElement > rightElement swap leftElement and rightElementswapped <- trueend bubbleSort
Applications of Bubble Sort Algorithm
Despite its simplicity and relatively modest time complexity, bubble sort has some applicability in specific contexts. Here are a couple of such examples:
Education: Bubble sorting is frequently used in educational contexts to introduce students to sorting algorithms. Because of its simple implementation and visualization, it is an excellent tool for teaching basic sorting techniques and algorithmic thinking.
Small Data Sets: Because of its simplicity and ease of implementation, bubble sort is ideal for sorting small data sets. When working with a limited number of components, the performance differences between sorting algorithms become less noticeable, and the simplicity of bubble sort can be helpful too.
Partially Sorted Data: Bubble sort can perform reasonably well if the data set is already partly or nearly sorted. Because bubble sort swaps neighboring elements, it can use the already sorted half of the list to reduce the required comparisons and swaps.
Adaptive Sorting: Bubble sort is an adaptive sorting algorithm, which means it can handle incoming data that is nearly sorted or has a small number of inversions efficiently. In such instances, the performance of bubble sort can be equivalent to that of more complicated algorithms.
Optimization of Sorting Algorithms: Because bubble sort is inefficient, it is a good choice for highlighting the need for more optimized sorting algorithms. When comparing the performance of bubble sort to quicker sorting algorithms, students can see the advantages of more advanced approaches such as quicksort, merge sort, or heap sort.
Benefits of Bubble Sort Algorithm
While bubble sort is not the most efficient sorting algorithm for massive data sets, it does have a few advantages in some situations:
Bubble sort is one of the most basic sorting algorithms to comprehend and implement. It entails simple comparisons and shifting of neighboring parts. Because of its simplicity, it is an ideal starting point for understanding sorting approaches and algorithms.
Simple to Implement: The bubble sort implementation is relatively simple and takes little code. It does not require sophisticated data structures or advanced concepts, making it suitable for even novice programmers.
Space Efficiency: Because bubble sort sorts in place, it does not require additional memory beyond the initial array. During swapping, it only needs a fixed amount of extra space for temporary variables. This can be useful when memory utilization is an issue.
Adaptive: Bubble sort is an adaptive method, meaning its speed can improve while dealing with partially or nearly sorted data. It uses the already-sorted portion of the array, requiring fewer comparisons and swaps in such circumstances.
Easy Sorting: Bubble sort is a stable sorting algorithm that keeps the relative order of elements with equal values. If two entries in the input list have the same value, their order in the sorted list is held. This characteristic is critical when maintaining the original order is required.
Optimized Bubble Sort Algorithm Implementation
In the following section of the article, we will look at implementing the Optimized Bubble sort algorithm in C++ and Java programming languages. Let us have a look at all of them.
C++ Code:
//Optimized bubble sort algorithm in C++ #include <iostream>using namespace std; //Perform bubble sortvoid bubbleSort(int array[], int size) { // loop to access each array element for (int step = 0; step < (size-1); ++step) { //Check if swapping occurs int swapped = 0; // loop to compare two elements for (int i = 0; i < (size-step-1); ++i) { // compare two array elements // change > to < to sort in descending order if (array[i] > array[i + 1]) { // swapping occurs if elements // are not in the intended order int temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; swapped = 1; } } //No swapping means the array is already sorted //So, no need for further comparison if (swapped == 0) break; }} //Print an arrayvoid printArray(int array[], int size) { for (int i = 0; i < size; ++i) { cout << " " << array[i]; } cout << "\n";} int main() { int data[] = {-32, 49, 23, 18, -97}; //Find the array's length int size = sizeof(data) / sizeof(data[0]); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:\n"; printArray(data, size);}
Output:
Sorted Array in Ascending Order:
-97 -32 18
23 49
Java Code:
//Optimized Bubble sort algorithm in Java
import java.util.Arrays;
class Main {
// perform the bubble sort
static void bubbleSort(int array[]) {
int size = array.length;
// loop to access each array element
for (int i = 0; i < (size-1); i++) {
//Check if swapping occurs
boolean swapped = false;
// loop to compare adjacent elements
for (int j = 0; j < (size-i-1); j++) {
// compare two array elements
// change > to < to sort in descending order
if (array[j] > array[j + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swapped = true;
}
}
//No swapping means the array is already sorted
// so no need for further comparison
if (!swapped)
break;
}
}
public static void main(String args[]) {
int[] data = { -9, 78, 23, 199, -5 };
// call method using the class name
Main.bubbleSort(data);
System.out.println("Sorted Array in Ascending Order is as follows:");
System.out.println(Arrays.toString(data));
}
}
Output:
The sorted Array in Ascending Order is as follows:
[-9, -5, 23, 78, 199]
Real-Life Applications of Optimized Bubble Sort Algorithm Implementation
Because of its slowness, bubble sort is rarely utilized for large-scale data sorting in practice.
However, in specific circumstances where the dataset or limitations fit with its strengths, an optimized implementation of bubble sort can still find some practical applications. Here are a couple of such examples:
Small Datasets: Bubble sorting can be effective for sorting small datasets with a limited number of elements. If the dataset is small enough that the time complexity of bubble sort isn't an issue, an optimized implementation can provide a straightforward solution.
Almost Sorted Data: An optimized bubble sort can be a good option if the data is nearly sorted or has few inversions. It uses the partially sorted nature of the data to reduce redundant comparisons and swaps, potentially outperforming more complex algorithms in some circumstances.
Embedded Systems: Because of its simplicity and low memory needs, bubble sort suits resource-constrained situations such as embedded systems or microcontrollers with limited processing power and memory. Where efficiency is not the main issue, an optimized bubble sort can give a simple sorting solution.
Benefits of Optimized Bubble Sort Algorithm Implementation
While bubble sort is not known for its efficiency, an optimized version of the algorithm can nonetheless provide some advantages in some situations:
Simplicity: Optimized bubble sort retains the fundamental bubble sort algorithm's simplicity and ease of implementation. It uses very little code and only simple comparisons and swaps. Because of its simplicity, it is simple to understand, implement, and debug.
Adaptive Sorting: Optimized bubble sort can benefit from partially or almost sorted data. It detects when no swaps are performed during a pass, suggesting that the list has already been sorted. This adaptive behavior avoids needless comparisons and swaps, which improves efficiency in some situations.
Stability: Like the standard bubble sort, the optimized bubble sort maintains the relative order of components with equal values. This stability can be critical when upholding the original order is vital, such as sorting items with many properties.
In-Place Sorting: Optimized bubble sort sorts in place, which means it doesn't need any more memory beyond the initial array. This can be advantageous when memory use is a problem, mainly when working with massive datasets where external memory may not be available.
Conclusion
Finally, bubble sort is a straightforward sorting algorithm that is simple to grasp and execute. Although inefficient for large datasets, it can be helpful for small datasets or teaching purposes. Bubble sort's optimized version improves efficiency by utilizing partially sorted data and minimizing redundant comparisons and swaps.
However, for real-world applications, more efficient sorting algorithms are often selected. Bubble sort and its optimized counterpart are valuable tools for learning and comprehending the fundamentals of sorting algorithms and algorithmic optimization.
Comments