Bubble Sort Program in C++ – [Algorithm with Explanation]

 

1. Bubble Sort Program in C++

In this program, we will enter the numbers randomly and these numbers are stored in the array. After entering the numbers the program will start executing and then after sorting the compiler will print sorted array on the screen.

C++

1

//Learnprogramo - programming made simple

2

#include<iostream>

3

using namespace std;

4

int main()

5

{

6

    int number, i, a[100], j, temp;

7

    cout<<"Enter total number of elements :";

8

    cin>>number;

9

    cout<<"Enter "<<number<<" numbers :";

10

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

11

    {

12

        cin>>a[i];

13

    }

14

    cout<<"Sorting array using bubble sort technique...\n";

15

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

16

    {

17

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

18

        {

19

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

20

            {

21

                temp=a[j];

22

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

23

                a[j+1]=temp;

24

            }

25

        }

26

    }

27

    cout<<"Elements sorted successfully..!!\n";

28

    cout<<"Sorted list in ascending order :\n";

29

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

30

    {

31

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

32

    }

33

}

Output:

Explanation:

First For Loop: First Iteration-

Assume user gives input of 5 numbers.

for(i=0;0<4;0++) The Condition is TRUE so it will enter in the second for loop.

Second For Loop: First Iteration-

for(j=0;0<5-0-1;0++) The Condition is TRUE so the compiler will enter in the if statement.

if(a[0]>a[1])->if(8>7) It means condition is TRUE so temp=10.Now a[j]=a[j+1]->a[0]=a[1]->a[0]=7. And a[j+1]=temp->a[1]=8. So the array will become 7 8 4 5 9 and j will be incremented by 1.

Second For Loop: Second Iteration-

for(j=1;1<5-0-1;1++) the condition is TRUE so the compiler will enter into if statement if(8>4) it means the condition is TRUE.

So like this process continuously goes on.

Improving Efficiency of Bubble Sort:

It is quite possible that the array gets sorted before all n-1 passes are complete. To avoid unnecessary passes, we have to check whether the array has got sorted at the end of each pass.

This can be done by finding out if an interchange was made in a pass. If no interchanges were done, it implies that the array has got sorted. It can be checked by using a flag.

Bubble Sort Improving Efficiency Algorithm:

1 Step: START.

2 Step: Pass=1.

3 Step: swap=FALSE.

4 Step: i=0.

5 Step: If x[i]>x[i+1] then Interchange x[i] and x[i+1] and Swap=TRUE.

6 Step: i=i+1.

7 Step: If i<=n-Pass-1 then go to step 5.

8 Step: If swap=FALSE then go to step 11.

9 Step: Pass=Pass+1.

10 Step: If Pass<n then go to step 3.

11 Step: STOP.

2. Improved Bubble Sort Program in C++

C++

1

//Learnprogramo - programming made simple

2

#include<iostream>

3

using namespace std;

4

int main()

5

{

6

    int n;

7

    cout<<"Enter number of element you want to store: ";

8

    cin>>n;

9

    int arr[n],i,j;

10

    cout<<"Enter array values:\n";

11

    //taking the array value 

12

    //from user

13

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

14

    {

15

        cin>>arr[i];

16

    }

17

    //here this flag will help

18

    //to optimise the solution

19

    //first initialise flag=1

20

    int flag=1;

21

    //Now we will sort the array

22

    //if my flag value is 1 then only 

23

    //the loop will execute

24

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

25

    {

26

        //here after each time of j loop

27

        // we will re-initialize the flag to 0

28

        flag=0;

29

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

30

        {

31

            //checking if previous value is

32

            //grater than next one or not

33

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

34

            {

35

                //temp will temporarly store

36

                //the value of arr[j]

37

                //then we will swap the values

38

                int temp=arr[j];

39

                arr[j]=arr[j+1];

40

                arr[j+1]=temp;

41

                //Here if there is a swap then

42

                // we will make it 1

43

                flag=1;

44

            }

45

        }

46

    }

47

    cout<<"After Bubble sort the array is:\n";

48

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

49

    cout<<arr[i]<<" ";

50

    return 0;

51

}

Output: