Insertion Sort C++

WHAT IS INSERTION SORT :

Insertion sort is a sorting algorithm which sorts the input data by putting elements into the sorted array one at a time .

It compares the next element in the array and puts it in the right place .

                                   Insertion Sort Graph


WHY INSERTION SORT :

When there are couple of sorting algorithms available why should i hit insertion sort ???

When the number of elements to be sorted is much lower , insertion sort gives us a very good result compared to others. Hence use it when the data set is low.

HOW INSERTION SORT WORKS :

Lets take an input tape with 5 elements in descending order.

5 4 3 2 1

4 5 3 2 1

3 4 5 2 1

2 3 4 5 1

1 2 3 4 5

On each iteration , it takes one element at a time and compares with the next element and places it in the right position.

First Iteration we take 4 as Key element . compare it with 5 . Since 4 is lesser we swap 4 and 5.

Second Iteration we take 3 as Key element . compare it with 5. 3 is lesser than 5 . Swap it . Yes, 3 is lesser than 4 also . Hence continue the swap until you place the element in the right place.

CODE FOR INSERTION SORT :


#include <iostream>
using namespace std;
void swap(int &a, int &b);

int main()
{
        // initializing the variables
        int a[10000];
        int c = 0;
        int n;

        // insert elements in descending order
        cin >> n;
        for(int i=n ; i>0; i--)
        {
        a[c] = i;
        c++;
        }

        // print the array before sorting
        cout << "Array Before Sorting" << endl;
        for(int i=0 ; i<n; i++)
                cout << a[i] << endl;

        // insertion sort logic starts here
        for(int i=0 ; i<n-1; i++)
        {
                int key = a[i+1];
                int pos = i+1;
                for(int j=i; j>=0 ;j--)
                {
                        if(a[pos] < a[j])
                        {
                                swap(a[pos],a[j]);
                                pos--;
                        }
                }
        }
        // insertion sort logic ends here. Printing the array after sort.
        cout << "Array AfterSorting" << endl;
        for(int i=0 ; i<n; i++)
                cout << a[i] << endl;
        return 0;
}

void swap(int &a, int &b)
{
        int t;
        t = a;
        a = b;
        b = t;

}

EXPLANATION :

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

Each time we need to pick an element and put it in the right place. Hence we need a loop that runs through an array.

int key = a[i+1];
int pos = i+1;

On each iteration we choose one element as key and place it in the right place.
Hence , we are choosing the element which is in i+1 place as key and noting down its position in variable pos.

for(int j=i; j>=0 ;j–)

This innner for loop helps to compare the previous elements . we need to check till the first element and place the key element at the right place.

if(a[pos] < a[j])
{
swap(a[pos],a[j]);
pos–;
}

This condition checks with the previous element . If it is greater then it swaps the element .

TRIAL

Lets run this program for 5 elements .

Now input tape contains 5 4 3 2 1

First Iteration :

i=0 , key = 4, pos = 1
j=0 , 0>=0 is true hence
if(4<5) swap(4,5); pos– => pos = 0
Now, input tape contains : 4 5 3 2 1

Second Iteration:

i=1, 1<5, key = 3 and pos = 2 j=1, 1>=0
if(3<5) – true swap(3,5); Now input tape contains 4 3 5 2 1 pos — => pos =1

j– => j=0
j=0; 0>=0
if(3 < 4) – true swap(3,4) pos– = > pos = 0
Now input tape contains 3 4 5 2 1

Simillary loop goes on sorting .

BEST , WORST AND AVERAGE CASES

The program given above is for worst case . since the elements are in descending order . In this case, we need to compare all the elements with 2 for loops . The time complexity will be quadratic

For Best case scenario put the elements in the sorted order.

 for(int i=0 ; i<5; i++)
        a[i] = i+1;

Eventhough the elements are in the sorted order, the outer for loop will be running for n comparisons. Hence the best case is O(N);

AVERAGE CASE :

Generate random numbers and insert it into array .

#include <stdlib.h>
 srand(time(NULL));
         for(int i=0 ; i<5; i++)
        {
                a[i] = rand() % 10 + 1;
        }

Even in this case, the time complexity goes quadratic.
Hence the insertion sort is suitable only for the nearly sorted low data elements.
Below table shows the best worst and average case analysis of the program.

N Best Worst Average
1024 0.004 0.008 0.008
2048 0.016 0.032 0.02
4096 0.048 0.116 0.084
8192 0.164 0.468 0.312
16384 0.62 1.92 1.248
32768 2.47 7.704 4.94
65536 9.8 30.372 19.876
131072 39.428 125.43 83.756

Using SQL OR and UNION operators

Whenever we write an sql , it is very important that we check the cost of it. If there is any room for improvement in the query based on the time taken by the query to fetch the result.

One such occasion is using an OR clause. There are certain situations where we need “Either this or that” kind of results . We are forced to use OR conditions on that query . But, i personally feel OR condition are little slower than UNION when we hit on the bigger tables .

The UNION query looks bigger , but it actually runs faster than the OR condition. Just for the clarity , am just adding a simple example where we need to find out the employee names and their salary if they have an income greater than 2000 or their past increment is higher than 200

we have the table structures given below

table name : emp
empid empname
1      alice
2      bob
3      david
4      charlie
table name : emp_sal
empid  salary  increment
1      1000     100
2      2000     200
3      4000     400
4      5000     500

by using or :

select e.empname, s.salary from emp e, emp_sal s where e.empid = s.emp_id and (s.salary > 2000 or s.increment > 200);

by using UNION :

select e.empname, s.salary from emp e, emp_sal s where e.empid = s.emp_id and s.salary > 2000
UNION
select e.empname, s.salary from emp e, emp_sal s where e.empid = s.emp_id and  s.increment > 200;

The union query looks bigger. But , it runs pretty faster than OR query .

Nurpyena — Vedic Mathematics

Anurpyena means propotionality. This method is helpful to find the product of two numbers when both of them near to common base 10. We can follow 3 approaches to solve a problem..

Approach 1 :

46 X 43

Take the base as the higher multiple of ten.. In above example, lets take 50..

Write the numbers and their differences to 50 as shown below

46          -04

43          -07

——————

now we have to follow the cross addiition

46          -04

43          -07

——————

(46-07) or (43-04)

multiply the differences and write the product on the left side

46          -04

43          -07

——————

39/(04*07)

39/28

Since base is 50 which is 100/2, we have to divide 39 by 2.

39/2 = 19 1/2.. which we can write as 19 and the half will be added to the right side answer .. (50 + 28)

Hence the answer is 1978..

Approach 2: If you find division process as difficult one you can go for this..

The steps are same as above.. But while taking the base we are going to take 50 which is 5 X 10(remember, in the last approach we took as 100/2).

46          -04

43          -07

——————

(46-07) or (43-04)

46          -04

43          -07

——————

39 / 28

Since, we took base 50 as 5 X 10 we have to multiply left part by 5 and add the first digit of right answer to it!

46          -04

43          -07

——————

39 X 5        8

+2

46          -04

43          -07

——————

(195 + 2) / 8 = 1978

Multiplying two numbers whose first figures are same and last figures add upto ten using Vedic Mathematics

Formula:

Na * Nb = (N+1) * N(a *b) where a + b = 10

Example:

54 * 56 = (5 +1) * 5(4 * 6)=(6 * 5)(4 * 6)= 3024

62 * 68 =(6+1) * 6(2 * 8)=(7 * 6 )(2 * 8)= 4216

Explanation:

If the tens digit of the two numbers is same and the unit digits add up to 10 then increment the number and multiply it with the value before incremented and multiply the unit digits .

Multiplication by 2 Vedic Mathematics

When we want to double the numbers we can follow two kind of approaches in it…

For example if we need to multiply 117 * 2

just take the first two digits and multiply it by 2…

before putting it see whether the third digit is less than 5..if not add one with the answer

now its 23. and just multiply unit digit with 2 and write the unit digit of answer..

234

simillarly 354 * 2

(35 * 2)(4 * 2)
7 0 8

and the second way of doing this is by separating the numbers

lets take the same example…117 is the number..

we can do it as (110 + 7) * 2 . because doubling 110 and 7 is easy and we can add fast..