Bubble Sort in Data Structures
In the Bubble Sort technique in data structures, the elements are compared to their adjacent elements. If the order is found to be wrong, then they are swapped. In this way, after an iteration, the last element comes to its correct position.
This is done, till all the elements are in their correct position.
Just like the movement of air bubbles in the water that rises up to the surface, each element of the array move to the end in each iteration. Therefore, it is called a bubble sort.
First, elements 9 and 3 are compared. 9 is found to be greater than 3 so, they are swapped among themselves.
After that element 9 is compared to element 12. The relative positions are found to be correct. So, no change happens.
Then, element 12 is compared to element 18, and the relative positions are found to be correct. So, no change.
After that, 18 is compared to 5 and the relative positions are found to be wrong. So, they are swapped among themselves.
In this way, at the end of the first iteration, the greatest element is inserted at the last position.
This process continues till all the elements in the array are sorted.
Now, we will see the code for this –
#include <iostream>
using namespace std;
void bubbleSort(int array[], int size) {
for (int step = 0; step < size; ++step) {
for (int i = 0; i < size - step; ++i) {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << array[i];
}
cout << "\n";
}
int main() {
int data[] = {9,3,12,18,5};
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
cout << "Sorted Array in Ascending Order:\n";
printArray(data, size);
}
Output –
3 5 9 12 18
Now, we will see the time complexity analysis for this algorithm –
Best Case – O(n)
Average Case – O(n^2)
Worst Case – O(n^2)
And the space complexity for this algorithm is O(1). Because we haven’t used any extra space to sort this array.
When is Bubble Sort Used?
Bubble sort is used if –
- complexity does not matter
- short and simple code is preferred
So, in this article, we learned about our first sorting algorithm which is bubble sorting. We will learn more sorting algorithms in upcoming articles.
