C++ Program to implement insertion sort [DEVCPP/GCC]

INSERTION SORT

Insertion sort is another sorting algorithm which sorts the list by shifting elements. It is simple to implement and works efficienty for smaller set of data. It "inserts" the key element in its correct position in the sorted subarray at each iteration.

EXAMPLE

Let us consider a list containing 5 elements i.e. 50,40,30,20,10 to be sorted in ascending order by insertion sort. Since a single element is considered sorted, thus it begins with the second index.At each iteration, a key element is selected such that the elements before key element are sorted.

In the first iteration, the element at index 0 is considered as sorted and element at index 1 is selected as key element (Here 40). The key element is stored in a temporary variable and then the shifting of elements is performed. Since 50>40, 50 shifts towards the key element's index making space for the key element. Since minimum index is reached and we are left with no more comparisons, we place the key element at this index.

In the second iteration, element at index 2 is selected as the key element (Here 30). Notice that the elements before 30 are already in sorted order, thus we only need to determine the correct position in that sorted subarray for our key element. Since 50 and 40 both are greater than 30, thus both are shifted towards key element's index and the key element(30) is placed in the correct position in that subarray.

In the third iteration, element at index 3 is selected as the key element (Here 20). 20 is again compared with its previous sorted elements for its correct position. 20 being smallest of all its previous elements obtains starting position in the sorted subarray

In the last iteration, the sorted subarray consists of n-1 elements of the list and the remaining element is selected as key element. This element is compared with its preceeding elements one by one and acquires its correct position in the array, thus all the elements in the array are sorted.

PROGRAM

// Program to implement insertion sort

#include <iostream>
#define MAX 5

using namespace std;

void insertion_sort(int a[],int size)
{
        int i,j,key;

        for(i=1;i<size;i++)
        {
                key=a[i];
                j=i-1;

                while((key<a[j]) && (j>=0))
                {
                        a[j+1]=a[j];
                        j--;
                }

                a[j+1]=key;
        }

        cout<<"\n\nSORTED ARRAY\n";

        for(i=0;i<size;i++)
        {
                cout<<a[i]<<" ";
        }
}


int main()
{
        int i,list[MAX];

        cout<<"ENTER ELEMENTS TO BE SORTED\n";
        for(i=0;i<MAX;i++)
        {
                cin>>list[i];
        }

        insertion_sort(list,MAX);

        return 0;
}

OUTPUT

C++ Program to implement queue through classes and objects [DEVCPP/GCC]

QUEUE

Queue is a linear data structure in which insertion take place at one end called rear end and deletion can take place from other end called front end. Queue implements First In First Out (FIFO) technique i.e. the oldest element is extracted first.

PROGRAM

// Program to implement queue through classes and objects

#include <iostream>
#define MAX 10

using namespace std;

class Queue
{
      int front,rear;
      int queue[MAX];

      public:

      Queue()
      {
              front=rear=-1;
      }

       void qinsert(int item)
       {
              if(rear==MAX-1)
             {
                      cout<<"\nQUEUE OVERFLOW";
             }
             else if(front==-1 && rear==-1)
             {
                      front=rear=0;
                      queue[rear]=item;
                      cout<<"\nITEM INSERTED: "<<item;
             }
             else
             {
                      rear++;
                      queue[rear]=item;
                      cout<<"\nITEM INSERTED: "<<item;
             }
       }

       void qdelete()
       {
              int item;

              if(rear==-1)
             {
                       cout<<"\nQUEUE UNDERFLOW";
             }
             else if(front==0 && rear==0)
             {
                       item=queue[front];
                       front=rear=-1;
                       cout<<"\n\nITEM DELETED: "<<item;
             }
             else
             {
                      item=queue[front];
                      front++;
                      cout<<"\n\nITEM DELETED: "<<item;
             }
       }

       void qtraverse()
       {
              if(front==-1)
              {
                      cout<<"\n\nQUEUE IS EMPTY\n";
              }
              else
              {
                      cout<<"\n\nQUEUE ITEMS\n";
                      for(int i=front;i<=rear;i++)
                      {
                               cout<<queue[i]<<" ";
                      }
                      cout<<endl;
              }
        }
};

int main()
{
      Queue q;

      q.qtraverse();
      q.qinsert(10);
      q.qinsert(20);

      q.qtraverse();

      q.qdelete();
      q.qinsert(30);

      q.qtraverse();
      return 0;
}

OUTPUT

C++ Program to implement stack through classes and objects [DEVCPP/GCC]

STACK

A stack is a linear data structure in which an element can be inserted or deleted only at one end called the top of the stack. A stack follows the principle of Last-In-First-Out (LIFO) i.e. Last inserted element will be retrieved first . 

According to the stack terminology, PUSH and POP are two terms used for insert and delete operations. This is a static implementation of stack through classes and objects.

PROGRAM

//Program to implement stack through classes and objects

#include <iostream>
#define SIZE 10

using namespace std;

class Stack
{
        int stack[SIZE],top;

        public:

        Stack()            //Constructor for initializing top
        {
                 top=-1;
        }

        void push(int num)
        {
                if(top==SIZE-1)    //Stack is full
                {
                         cout<<"\nSTACK OVERFLOW";
                }
                else
                {
                        top++;
                        stack[top]=num;
                }
        }

        void pop()
        {
                int num;
                if(top==-1)         //Stack is empty
                {
                        cout<<"\nSTACK UNDERFLOW";
                }
                else
                {
                        num=stack[top];
                        top--;
                        cout<<"\nELEMENT DELETED: "<<num;
                }
        }

        void traverse()
        {
                if(top==-1)
                {
                        cout<<"\nSTACK IS EMPTY";
                }
                else
                {
                       cout<<"\n\nSTACK ELEMENTS\n";

                       for(int i=top;i>=0;i--)
                       {
                                 cout<<stack[i]<<endl;
                       }
               }
       }

};

int main()
{
        Stack s;

        s.traverse();

        s.push(10);
        s.push(20);
        s.push(30);

        s.traverse();

        s.pop();

        s.traverse();
        return 0;
}

OUTPUT

C++ Program to display the diagonal elements of a given matrix [DEVCPP/GCC]

PROGRAM

//Program to display the diagonal elements of a given matrix

#include <iostream>
#define N 3

using namespace std;

int main()
{
        int i,j,Matrix[N][N];

        cout<<"\nENTER MATRIX\n";
        for(i=0 ; i<N ; i++)
        {
                for(j=0 ; j<N ; j++)
                {
                        cout<<"ENTER ["<<i<<"]["<<j<<"] ELEMENT: ";
                        cin>>Matrix[i][j];
                 }
        }

        cout<<"\nGIVEN MATRIX:\n";
        for(i=0 ; i<N ; i++)
        {
                for(j=0 ; j<N ; j++)
                {
                         cout<<Matrix[i][j]<<"  ";
                }
                cout<<endl;
        }

        cout<<"\nDIAGONAL ELEMENTS\n";

        cout<<"\nFIRST DIAGONAL: ";
        for(i=0 ; i<N ; i++)
        {
                 cout<<Matrix[i][i]<<"  ";
        }

        cout<<"\nSECOND DIAGONAL: ";
        for(i=0,j=N-1 ; i<N ; i++,j--)
        {
                cout<<Matrix[i][j]<<"  ";
        }

         return 0;
}

OUTPUT

C++ Program to calculate factorial of a given number [DEVCPP/GCC]

STEPS

1. Initialize variable fact with 1.
                  fact = 1;

2. Multiply fact with the given number.
                 fact = fact * num;

3. Decrement number by 1.
                    num-- ;

4. Repeat steps 2-3 till num>0.

PROGRAM

//Program to calculate factorial of a given number

#include <iostream>

using namespace std;

int main()
{
        int i,n;
        long fact=1;

        cout<<"ENTER THE NUMBER: ";
        cin>>n;

        while(n!=0)
        {
                fact=fact*n;
                n--;
        }

        cout<<"FACTORIAL IS: "<<fact;
        return 0;
}

OUTPUT

C++ Program to check whether given number is Strong number or not [DEVCPP/GCC]

STRONG NUMBER

A number is said to be a strong number if the sum of factorial of its individual digits is equal to the number itself.

eg. 145 = 1! + 4! + 5!
             = 1 + 24 + 120
             = 145

PROGRAM

//Program to check whether given number is Strong number or not

#include <iostream>

using namespace std;

int factorial(int n)
{
         int fact=1;

         while(n>0)
        {
                fact=fact*n;
                n--;
         }

         return fact;
}

int main()
{
        int num,numc,digit,sum=0;

        cout<<"ENTER NUMBER: ";
        cin>>num;

        numc=num;

        while(numc>0)
        {
                digit=numc%10;
                sum=sum+factorial(digit);
                numc=numc/10;
        }

         if(num==sum)
         {
                cout<<num<<" IS A STRONG NUMBER";
         }
         else
         {
               cout<<num<<" IS NOT A STRONG NUMBER";
         }

         return 0;
}

OUTPUT

C++ Program to calculate and print the roots of a quadratic equation [DEVCPP/GCC]

PROGRAM

//Program to calculate and print the roots of a quadratic equation!

#include<iostream>
#include<math.h>

using namespace std;

int main()
{
float a,b,c, delta,root1,root2;

cout<<"ENTER three numbers a, b and c of ax^2+bx+c:\n";
cin>>a>>b>>c;

if(!a)
cout<<"VALUE CANNOT BE ZERO"<<"\nABORTING!!!...\n";
else
{
delta= (b*b) - (4 * a * c);

if(delta>0)
{
root1= (-b + sqrt(delta))/(2*a);
root2= (-b - sqrt(delta))/(2*a);
cout<<"ROOTS ARE REAL AND UNEQUAL:\n";
cout<<"Root1="<<root1;
cout<<"\nRoot2="<<root2;
}
else if(delta==0)
{
root1= -b/(2*a);
cout<<"ROOTS ARE REAL AND EQUAL:\n";
cout<<"Root1="<<root1;
cout<<"Root2="<<root1;
}
else
{
cout<<"ROOTS ARE COMPLEX AND IMAGINARY \n";
}
}
return 0;
}

OUTPUT

C++ Program to replace a character with a given character in a string [DEVCPP/GCC]

PROGRAM

//Program to replace a character with a given character in a string 

#include <iostream>

using namespace std;

int main()
{
        int i,len;
        string str;
        char s_char, r_char;

        cout<<"ENTER STRING: ";
        getline(cin,str);

        cout<<"\nENTER CHARACTER TO BE REPLACED: ";
        cin>>s_char;

        cout<<"\nENTER REPLACING CHARACTER: ";
        cin>>r_char;

        len=str.length();

        for(i=0 ; i<len ; i++)
        {
                if(str[i]==s_char)
                {
                         str[i]=r_char;
                }
        }

        cout<<"\nMODIFIED STRING: "<<str;

        return 0;
}

OUTPUT

C++ Program to calculate sum of two numbers without using arithmetic operator [DEVCPP/GCC]

EXPLANATION

Let the two numbers a and b be 3 and 2. These numbers are represented in binary as:

3 = 011

2 = 010

ITERATION 1

I. Calculate carry (carry = a & b)

a:   0 1 1

b:   0 1 0

     _____
      0 1 0 

II. Calculate sum (a = a ^ b) (XOR operation)

a:   0 1 1

b:   0 1 0

      _____
       0 0 1

III. Update the value of b (b = carry << 1)

b  =  carry << 1
b  =  0 1 0 << 1
b  =  1 0 0

ITERATION 2

I. Calculate carry (carry = a & b)

a:   0 0 1
b:   1 0 0
     _____
      0 0 0

II. Calculate sum (a = a ^ b)

a:   0 0 1
b:   1 0 0
     _____
      1 0 1

III. Update the value of b (b = carry << 1)

b  =  carry << 1
b  =  0 0 0 << 1
b  =  0 0 0

Since, b has become 0, the calculation stops and leads us with sum as 1 0 1(5).

PROGRAM

// Program to calculate sum of two numbers without using arithmetic operator

#include <iostream>

using namespace std;

int main()
{
        int a,b,carry;

        cout<<"ENTER A: ";
        cin>>a;

        cout<<"ENTER B: ";
        cin>>b;

        while (b != 0)
        {
              carry = (a & b) ;
              a = a^b;
              b = carry << 1;
        }
     
        cout<<"SUM : "<<a;
 
        return 0;
}

OUTPUT