**Problem :-**Write A C++ Program For Bubble Sort Using Array

**Logic :-**

**Step-By-Step Example**.

Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared. Three passes will be required.

( 5 1 4 2 8 ) to ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1. ( 1 5 4 2 8 ) to ( 1 4 5 2 8 ), Swap since 5 > 4 ( 1 4 5 2 8 ) to ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) to ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

source-Wikipedia

**First Pass**( 5 1 4 2 8 ) to ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1. ( 1 5 4 2 8 ) to ( 1 4 5 2 8 ), Swap since 5 > 4 ( 1 4 5 2 8 ) to ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) to ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

**Second Pass**

( 1 4 2 5 8 ) to ( 1 4 2 5 8 )

( 1 4 2 5 8 ) to ( 1 2 4 5 8 ), Swap since 4 > 2

( 1 2 4 5 8 ) to ( 1 2 4 5 8 )

( 1 2 4 5 8 ) to ( 1 2 4 5 8 )

Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

**Third Pass**

( 1 2 4 5 8 ) to ( 1 2 4 5 8 )

( 1 2 4 5 8 ) to ( 1 2 4 5 8 )

( 1 2 4 5 8 ) to ( 1 2 4 5 8 )

( 1 2 4 5 8 ) to ( 1 2 4 5 8 )

**Complexity :-**

Best-Case --> O(n)

Average-Case-->O(n^2)

Worst-Case-->O(n^2)

Worst-case space complexity-->O(1) auxiliary

**Note :-**Bubble Sort Complexity O(n^2) in All Cases But if All Element in An Array is Already Sorted the We put a Special Condition if All Element Are Sorted then No Further Iteration And Loop Stop .

See How Bubble Sort Works .

This is a Extended Version of Bubble Sort You can Also Edit For Minimum Iteration Try By Own .

Try This C++ Program For Selection Sort

**Solution :-**

#include<iostream>

#include<stdlib.h>

using namespace std;

int main()

{

//By-Ghanendra Yadav

int a[100],i,s,j,temp,nochanges;

cout<<"ENTER THE SIZE OF ARRAY : "<<endl;

cin>>s;

cout<<"Enter The Elememnt In Array \n"<<endl;

for(i=0;i<s;i++)

{

cin>>a[i];

}

for(i=0;i<s;++i)

{

nochanges=0;

for(j=0;j<(s-1);++j)

{

if(a[j]>a[j+1])

{

temp = a[j];

a[j] = a[j+1];

a[j+1] = temp;

nochanges++;

}

}

if(nochanges==0)

break;

}

cout<<"\nSorted Array In Accending Order \n"<<endl;

for(i=0;i<s;i++)

{

cout<<a[i]<<" ";

}

cout<<"\n\nSorted Array In Decending Order \n"<<endl;

for(i=s-1;i>=0;i--)

{

cout<<a[i]<<" ";

}

return 0;

}

**See Also :-**

**Output:-**

## 0 Comments: