In this tutorial, we will learn to write an algorithm called bubble sort, one of the most popular and simple sorting techniques. Here, as a data structure, a dynamic array will be used where the memory will be allocated dynamically in the array as required.
The main idea of bubble sort is to compare two adjacent elements in an array and if they are arranged correctly we will move to the next element otherwise we will swap their positions. Similarly, we will keep on comparing the elements till the end of the array. There will be some consecutive passes and after every pass, one more will be at its correct position starting from the last one. After the first pass, it's time to make the second-largest position be filled with correct elements and so on...
Note: Also if we are required to apply bubble sort on an array of characters then by default we are asked to arrange them alphabetically.
Bubble Sort Algorithm
1- Compare and swap iteration
Step1: Starting from the first index, compare the first and the second elements.
Step2: If the first element is greater than the second element, they are swapped.
Step3: Now, compare the second and the third elements. Swap them if they are not in order.
Step4: The above process goes on until the last element.
2- Process the remaining iteration
Step5: The same process goes on for the remaining iterations. After each iteration, the largest element among the unsorted elements is placed at the end.
Step 6: The array is sorted when all the unsorted elements are placed at their correct positions.
C++ Program For Bubble Sort (Method 1)
#include<iostream>
using namespace std;
int bubble_sort(int n,int array[]){
int temp;
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-1;j--){
if(array[j]>array[j+1]){
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
return 0;
}
int main(){
int arr[]={5,6,9,2,3};
int n = sizeof(arr)/(sizeof(arr[0]));
bubble_sort(n,arr);
cout<<"Elements after sorting of the array:- "<<endl;
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
return 0;
}
Elements after sorting of the array:
2 3 5 6 9
C++ Program For Optimized Bubble Sort (Method 2)
This approach will work effectively when some of the elements of the array are already sorted and we need to placa e few elements at their proper positions.
#include<iostream>
using namespace std;
int bubble_sort(int n,int array[]){
int temp,flag;
for(int i=0;i<n-1;i++){
flag=0;
for(int j=0;j<n-i-1;j++){
if(array[j]>array[j+1]){
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
flag=1;
}
}
if(flag==0){
break;
}
}
return 0;
}
int main(){
int arr[]={5,3,8,6,9,1};
int n=sizeof(arr)/sizeof(arr[0]);
bubble_sort(n,arr);
cout<<"Elements after sorting the array are:- "<<endl;
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
return 0;
}
Elements after sorting the array are:
1 3 5 6 8 9
Conclusion
Here, we have learned to implement bubble sort using dynamic array through two different approaches one is a generalized approach whereas the second is an optimized one that works for a few selected but efficient arrays.
