Bubble Sort
Goal: Sorting a given array Using Bubble Sort.
Method-Used: Simple logic (Bubble Sort)
Description: Bubble sort is a simple sorting algorithm in which each element is compared with its adjacent one and if they are in wrong order ,they will be swapped. Program ends when all elements are in order and there is no more swapping needed.It is also known as "Comparison Sort".
Example:-
3 9 8 7 2
Pass-1--------------
3 9 8 7 2 ->>> 3 9 8 7 2
3 9 8 7 2 ->>> 3 8 9 7 2
3 8 9 7 2 ->>> 3 8 7 9 2
3 8 7 9 2 ->>> 3 8 7 2 9
Pass-2--------------
3 8 7 2 9 ->>> 3 8 7 2 9
3 8 7 2 9 ->>> 3 7 8 2 9
3 7 8 2 9 ->>> 3 7 2 8 9
Pass-3--------------
3 7 2 8 9 ->>> 3 7 2 8 9
3 7 2 8 9 ->>> 3 2 7 8 9
Pass-4--------------
3 2 7 8 9->>> 2 3 7 8 9
-->>If you look carefully above in every pass one element get its right position in array(Reamaining Largest One).
Program:-
#include<iostream>
using namespace std;
#include<conio.h>
int main() {
int a[10],i,k,n,temp;
cout<<"\n\tHow many Numbers you want to Enter\n";
cout<<"\t";
cin>>n;
cout<<"\tEnter numbers:\n";
for(i=0;i<n;i++)
{
cout<<"\t";
cin>>a[i];
}
for(i=0;i<n-1;i++)
{
k=0;
while(k<n-1-i)
{
if(a[k]>a[k+1])
{
temp=a[k];
a[k]=a[k+1];
a[k+1]=temp;
}
k++;
}
cout<<"\n\nAfter Pass->"<<(i+1)<<"->>";
for(int j=0;j<n;j++)
{
cout<<"\t";
cout<<a[j];
}
}
cout<<"\n\n\tFully Sorted Array is:-\n";
for(i=0;i<n;i++)
{
cout<<"\t";
cout<<a[i];
}
getch();
return 0;}
Output:-
Complexity:-
1.Best Case-: When list is already sorted.
Complexity is f(n)=O(n)
As we can see there is n-1 comparison during first pass ,(n-2) during second pass and so on.
then f(n)= (n-1)+(n-2)+(n-3)+......+1=n(n-1)/2
f(n)=O(n2).
*
0 comments:
Post a Comment