Skip to main content

Bubble Sort in C++ with improvements

Here is an example of Bubble sort in C++.  The example will perform bubble sort on a set of 10 integers. The example is a OO example . So everything is in a class called bubble. The class it self has following methods in it.

  • set() This will allow to set the values in the array.
  • show() This will display the given array.
  • sort1() normal bubble sorting.
  • sort2() improved bubble sorting.
Bubble sort : The sort is a very easy to implement sort method that compares the element to its next element. If the element is bigger then the first element then it is swapped with next element. The name bubble sort comes from the fact, the method is similar to bubble rising in water. As lighter bubble come up and heavy bubble fall down. So if you have numbers like
41,13,53,6
first 41 will be checked against 13. Since its bigger then 13 so it will be replaced with 13.
13,41,53,6
Now 2nd element which happens to be 41 will be compared to 53. since its smaller then 53 so we do nothing.
13,41,53,6
Next compare the next element 53 with 6. Since it is bigger then 6, it will be replaced by 6..
13,41,6,53
This is over result after First pass. Notice how the biggest element is at last position already. So we won't bother about it . Next we will repeat the process for the other elements.
After second pass
13,6,41,53
after 3rd pass 
6,13,41,53
Hence the array gets sorted.
Improvement : So how can bubble sorting be improved. Well the improvement can only happen if in between the passes the array gets sorted out. So when this happens we don't need to proceed checking the whole passes. How to detect if the array was sorted ?? well if there are no exchange of variables in any pass that means the array elements are already sorted out. We can use a variable "swap"  , we will set it to 0 just before any pass. and we will set it to 1 if any exchange happens. after the pass we will check its value, if its 0 that means no exchange happened so the array is already sorted by bubble sort. and we can break from there.
code:

#include<iostream>

using namespace std;

class bubble
{
    // 10 element of type int
    int a[10];
    
    public:
    bubble()
    {
        //default constructor sets all elements to 0
        for(int x=0;x<10;x++)
        {
            a[x]=0;
        }
    }
    void set()
    {
        cout<<"\n Enter Elements of Array=";
        for(int x=0;x<10;x++)
        {
            cout<<"\nEnter"<<x+1<<" Item=";
            cin>>a[x];
        }
    }
    void show()
    {
        cout<<"\n Printing Array=";
        for(int x=0;x<10;x++)
        {
            cout<<"\n"<<a[x];
        }
    }
    void sort1()
    {
        int moves=0;
        
        for(int x=0;x<10;x++)
        {
            for(int y=0;y<10-x-1;y++)
            {
                //compare the 2 near values
                // move the bigger one down by swapping
                if(a[y]>a[y+1])
                {
                    //swapping by a third variable
                    int t=a[y];
                    a[y]=a[y+1];
                    a[y+1]=t;    
                    
                }
                //count moves
                    moves++;
                
            }
        }
        cout<<"\n array sorted with "<<moves<<" moves";
    }
    void sort2()
    {
        int moves=0;
        int swap=0;
        for(int x=0;x<10;x++)
        {
            //set variable swap to 0
            swap=0;
            for(int y=0;y<10-x-1;y++)
            {
                //compare the 2 near values
                // move the bigger one down by swapping
                if(a[y]>a[y+1])
                {
                    //swapping by a third variable
                    int t=a[y];
                    a[y]=a[y+1];
                    a[y+1]=t;    
                    //if swapping is done set swap to 1
                    swap=1;
                    
                }
                //count moves
                    moves++;
                    
                
            }
            if(swap==0)
            {
                // break the loop if no swapping were done 
                // this will only happen if the array was sorted already
                break;
            }
        }
        cout<<"\n array sorted with "<<moves<<" moves";
    }
};

int main()
{
    bubble b;
    b.set();
    b.show();
    b.sort2();
    b.show();
}

Popular posts from this blog

Find nth Prime Number in C++

c++ program to find prime numbers: The problem of finding prime number can be solved by checking all numbers, testing them for prime and then moving ahead. If you want to calculate nth prime. Then this can be done in a brutal way by checking the number one by one. This may sound odd, by there is no easy way then this  for prime numbers (Well Actually there are like Pollard's Rho Algorithm, Number Sieves or Shor's Quantum Algorithm, but we are talking about the one that most people may understand easily). There may be way to pre-calculate the prime numbers but that again is not sufficient. So how can we use c++ to create a program to find prime numbers.

Program to find nth Prime number in C

Objective: To print any Prime number in C.  This task may sound easy but is a very good exercise to help optimize CPU intensive programs. Finding Prime number is a very CPU hogging task and it becomes even more dreaded as the number starts to grow. Lets say we want to find 30001th prime. how will we find it?? Here is the program. Programming logic : The easiest method is to check if the given number N is divisible by any number from 2 to N-1. But it may be noted that we don't need to go beyond the number that is square root of N.  why?? lets have a look. Say we are testing number 49 for prime number. Our objective is to find any number that may divide it. so we start from 2,3,4 etc. As soon as we cross 7 there will be no number that will divide 49, if there was we have got it earlier since it will be smaller then 7.  Get it? another example 64 : 2x32 4x16 8x8 16x4 32x2 as you can see when we pass number 8 we don't need to test as the number that will come ,...