C++ Program for Bubble Sort
Description
In bubble sort each element is compared with its adjacent element.
If first element is larger than the second one then the position of the elements are interchanged, otherwise it is not changed.
Then next element is compared with its adjacent element and the same process is repeated for all elements of array.
During first pass, largest element occupies last position, during next pass same process is repeated leaving the second largest element at second last position.
Same process is repeated until no more elements are left to be compared. Finally array is sorted.
Lets see one example
consider the array given below.
11 15 2 13 6
Pass-1
11(swapped) 2 2 2 2
2 11(no swapping) 11 11 11
15 15 15(swapped) 13 13
13 13 13 15(swapped) 6
6 6 6 6 15
Last element is sorted .(i.e 15)
Pass-2
2 (no swapping) 2 2 2
11 11(no swapping) 11 11
13 13 13(swapped) 6
6 6 6 13
15 15 15 15
Last two elements are sorted .(i.e 15 , 13)
Pass-3
2(no swapping) 2 2
11 11(swapped) 6
6 6 11
13 13 13
15 15 15
Time complexity = O(N2
Space complexity =O(1)
C++ Program for Bubble Sort
using namespace std;
void Bubble_sort(int a[], int n)
{
int temp,i,j;
for(i=0 ; i<n ; i++)
{
for(j=0 ; j<n-i-1 ; j++)
{
if( a[j] > a[j+1] )
{
temp=a[j]; //swap a[j] and a[j+1];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
int main() {
int n,i;
cout<<"No. of elements in array\n";
cin>>n;
int a[n];
cout<<"Elements of array\n";
for(i=0 ; i<n ; i++)
{
cin>>a[i];
}
Bubble_sort(a,n);
cout<<"Sorted array is as follow\n";
for(i=0 ; i<n ; i++){
cout<<a[i]<<"\n";
}
return 0;
}
Output
No. of elements in array ?
5
Enter elements of array
11
2
13
15
6
Sorted array is as follow
2
6
11
13
15
Comments