Bubble Sort

Algorithm::

k ← n //number of elements of array

    while k ≠ 0

              t ← 0

              for j=1 to k-1 do

                    if x_j > x_j+1 then   //here j is the index number

                        x_j ↔ x_j+1    

                             t ← j

               k ← t

Explanation::

Suppose we have an unsorted array like 8,7,5,1,12 , we have to sort this array at ascending order . We use bubble sort for sorting this array .

The algorithm of bubble sort is, it compare two numbers and when the if condition will true it swap two number to each other. At ending of every iteration the last number always will be highest number or lowest number according your condition .

Now, we see how to work this algorithm:

Iteration :: 1

Loop will be started from index 1 and ended at k-1 so, at 1st iteration loop will be cycled 4 times.

j=1,  8     7     5     1     12 ;  t=1

             swap

j=2,  7     8     5     1     12 ;  t=2
                       swap

j=3,  7     5     8     1     12 ;  t=3

                                  swap

j=4,  7     5     1     8     12 ;  t=3
                                            no swap

k=3;

After 1st iteration the array will be 7,5,1,8,12 

and k will be 3, cause after loop we assign the value of t at k.

Iteration :: 2

At this time the loop will be cycled k-1= 3-1= 2 times.

j=1  7     5     1     8     12 ; t=1
          swap

j=2  5     7      1     8     12 ; t=2
                    swap

k=3;

After 2nd iteration the array will be 5,1,7,8,12 and k will be 2

Iteration :: 3 

At this time the loop will be cycled k-1= 2-1= 1 times.

j=1  5     1     7     8     12 ;  t=1
       swap

k=1;

Iteration :: 4
t=0;
k=0;

After 3rd iteration the array will be 1,5,7,8,12 and k will be 1. This is our final array. But the while loop will be continued cause the loop condition still now true. At 4th iteration at starting time (t assigned by 0 at every iteration) t will be assigned by 0. But the for loop will not be executed at this time. So, k will be assigned by 0 and the while loop will be false next time.


CODE ::

#include <iostream>
using namespace std;
int main ()
{
    int array[100],n;
    cout<<"Enter Number of Elements:"<<endl;
    cin>>n;
    cout<<"Enter Elements:"<<endl;
    for(int i=1;i<=n;i++)
        cin>>array[i];
    int k = n;
    while(k!=0)
    {
        int t=0;
        for(int j=1;j<=k-1;j++)
        {
            int temp;
            if(array[j]>array[j+1])
            {
                temp = array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
                t=j;
            }
        }
        k=t;
    }
    for(int i=1;i<=n;i++)
        cout<<array[i]<<" ";
    return 0;

}