Bubble Sort in C++

It is a sorting process in which two nearby values are compared and then exchanged if need arises.

       Suppose A is an array consisting of 5 integers as shown

A[0]= 17,    A[1]= 14,    A[2]= 10,    A[3]=7,    A[4]=3

    This array has to be arranged in an ascending order using bubble sort method. The step and comparison involved while arranging the array are listed below.

STEP 1

17  14  10  7  3                     17>14  so exchange 17 and 14

14  17  10  7  3                     17>10  so exchange 17 and 10

14  10  17  7  3                     17>7  so exchange 17 and 7

14  10  7  17  3                     17>3  so exchange 17 and 3

14  10  7  3  17

Thus after step 1 the largest value is shifted to last position.

STEP 2

14  10  7  3  17                     14>10  so exchange 14 and 10

10  14  7  3  17                     14>7  so exchange 14 and 7

10  7  14  3  17                     14>3  so exchange 14 and 3

10  7  3  14  17

Thus step 2 requires 3 comparisons and the second largest value is shifted to second last position.

STEP 3

10  7  3  14  17                     10>7  so exchange 10 and 7

7  10  3  14  17                     10>3  so exchange 10 and 3

7  3  10  14  17

Thus after step 3 third largest value is shifted to third last value.

STEP 4

7  3  10  14  17                     7>3  so exchange 7 and 3

3  7  10  14  17

Step 1 uses 4 comparisons. Step 2 needs 3 comparisons and so on. The array A requires 4 steps where each step uses 5-step value comparisons. Therefore a list having n values needs n-1 steps with each step using n- step value comparison. So order is O(n²).

Algorithm:- Suppose that an array ‘A’ having n numbers has to be arranged in an ascending order. The bubble sort algorithm can be used to accomplish the same.

STEP 1:- Repeat step 2   for i=0 to n-2

STEP 2:- Repeat step 3   for j=0 to n-1-i

STEP 3:- if (A[j] > A[j+1] )

                                swap A[j] and A[j+1]

                end of if;

                end of step 2;

end of step 1;

STEP 4:- STOP

C++ Programme code

#include<iostream>

#include<iomanip.h>

void main()

{

     int a[50], n;

     cout<< “Enter the size of list ”;

     cin>>n;

     cout<< “Enter”<<n<< “values”;

     for(int i=0; i<n; i++)

           cin>> a[i];

     for(i=0; i<n-1; i++)

           for(int j=0; j<n-1-i; j++)

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

                {

                     int t = a[j];

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

                     a[j+1] = t;

                 }

     cout<< “Arranged list is...”;

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

           cout<< setw(5) << a[i];

}