## Sorting – Insertion sort

Insertion Sort

Sorts a set of records by comparing the next record with all the previous elements.  Compare next element with previous.  If next element is smaller than previous element, then swap both the elements. i.e.
if(arr[j]>arr[i])
swap(arr[j],arr[i);

Example:      The loop may be written as follows:

for I = 2 to n
for j = I-1 to >=1
if(arr[I] < arr[j])
swap(arr[i],arr[j]);

Insertion sort is considered best if most of the data is in sorted order.

Efficiency:

I                           j                   number of times

2                      1 to 1                            1

3                      2 to 1                            2

4                      3 to 1                            3

–                       ——                             –

–                       ——                             –

–                       ——                             –

(n-1)                 (n-2) to 1                      (n-2)

n                      (n-1) to 1                      (n-1)

Sum of terms: 1+2+3+…………..+(n-2)+(n-1)

=(n-1)(n-1+1)/2
=n(n-1)/2
=n2/2-n/2
=0.5n2-0.5n
=O(n2)

Note:

An insertion sort may be viewed as a general selection sort in which the priority queue is implemented as an ordered array.  We have to only insert elements in priority queue.  Once the elements have been inserted, they are already sorted, so that no selection is necessary.

Shell sort is an improvised form of insertion sort, as for k=1, most of the data which is processed is already sorted.

Insertion Sort Program:

#include <stdio.h>
#include <conio.h>
#define MAX 10
void main()
{
int arr[MAX];
int i,j,temp,num,ct;
clrscr();
for(i=0;i<MAX;i++)
{printf(“Enter array elements?”);
scanf(“%d”,&arr[i]);
}
for(i=1;i<MAX;i++)
{
num=arr[i];
ct=i;
for(j=i-1;j>=0;j–)
{if(num<arr[j])
{
temp=arr[ct];
arr[ct]=arr[j];
arr[j]=temp;
ct=j;
}
}
}
printf(“Sorted array using insertion sort is:\n”);
for(i=0;i<MAX;i++)
printf(“%d\t”,arr[i]);
getch();
}

## Sorting – Bubble sort

Bubble sort:
Two consecutive elements are compared.  It sorts the elements in right to left fashion.  Thus, (n-i) comparisons are made.

Example:      Frequency:

i                       j                       number of times
———————————————————————————————
1                                             1 to n-i                          n-1
2                                             1 to n-i                          n-2
3                                             1 to n-i                          n-3
–                                                  –                                –
–                                                  –                                –
–                                                  –                                –
n-1                                       1 to n-(n-1)                        1

Thus, 1+2+……………+(n-3)+(n-2)+(n-1)

which is sum of (n-1) terms.

=(n-1)(n-1+1)/2
=(n-1)n/2
=n2/2 – n/2
=0.5n2-0.5n

Thus, efficiency in Big(O) Notation is O(n2).

i)  Best Case:  Data is already in sorted form.  Thus no interchange occurs.

Number of comparisons may be reduced as follows:

for i=1,  j=n-i   ie. (n-1)

Frequency is (n-1), which is achieved if we quit after scan, when no interchange occurs.

Hence, efficiency is O(n).

ii)  Worst Case:  Data is in reverse order.  Each value gets interchanged.  Hence number of comparisons will be same as calculated above. i.e.

Efficiency = O(n2)

iii)  Average Case:

(Best Case + Worst Case)/2

= ((n-1) + n2)/2

=(n/2)-(1/2)+(n2/2)

Efficiency = O(n2)

Bubble sort program with n2 frequency and an efficiency of O(n2)

#include <stdio.h>
#include <conio.h>

#define n 10

void main()
{
int arr[n], i,j,temp;
clrscr();
printf(“\nInitializing array…!”);
for(i=0;i<n;i++)
{
printf(“\nEnter elements?”);
scanf(“%d”,&arr[i]);
}
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
{
if(arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
printf(“\nSorted array using Bubble sort is:\n”);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
getch();
}

Bubble sort program with best efficiency O(n) and frequency (n-1)

#include <stdio.h>
#include <conio.h>

#define n 5

void main()
{
int arr[n], i,j,temp,sort=0;
/*sort=0 for false and sort=1 for true i.e. sorted array*/
clrscr();
printf(“\nInitializing array…!”);
for(i=0;i<n;i++)
{
printf(“\nEnter elements?”);
scanf(“%d”,&arr[i]);
}
for(i=0;i<n-1 && sort!=1;i++)
{
for(j=0;j<n-i-1;j++)
{
sort=1;
if(arr[j]>arr[j+1])
{
sort=0;
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
printf(“\nSorted array using Bubble sort is:\n”);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
getch();
}

## Sorting – Shell sort

Shell Sort:

Shell sort is quite similar to that of insertion sort with the only difference that in shell sort, higher values of k are considered.  Whereas insertion sort assumes k to be 1.  If k=4, then every 4th element is compared, if it is 3 then every 3rd element is compared.  Thus k=m means every mth element gets compared with each other and is swapped.

The value of k is decremented after each scan.  The file is sorted, when k becomes 1 and swapping is performed for k = 1.  The difference in original and decremented value(i.e. difference in k) may be generated using a hash function, which returns the number of decrements in k. say k=4, then k=2 and finally k=1.  k=3 is skipped.  or (k=8, k=4, k=2, k=1) or (k=4, k=3, k=2, k=1).

If k is taken as 1 only, then it is no more shell sort, it becomes insertion sort.

Example:   /*Program to implement Shell Sort*/

#include <stdio.h>
#include <conio.h>

#define MAX 5

void shellsort(int x[],int n,int incrmnts[],int numinc)
{
int incr,j,k,span,y;
for(incr=0;incr<numinc;incr++)
{
span=incrmnts[incr];
for(j=span;j<n;j++)
{
y=x[j];
for(k=j-span;k>=0 && y<x[k]; k-=span)
x[k+span]=x[k];
x[k+span]=y;
}
}
}
/*
A hash function may be defined as follows:
Let n be the size of the array (total number of elements).
Then begin from (n-3) upto 1.
Example: Let there are 8 elements, then n=8
increments array will hold 5,3,1 for (n-3), (n-5), (n-7) respectively.
and ct=3, where ct is numinc.
*/

int hash(int arr[],int n)
{
int i,j=0,ct=0;
for(i=3;(n-i)>0;i+=2)
{
arr[j++]=n-i;
ct++;
}
if(arr[j-1]!=1)
{arr[j]=1;
ct++;
}
return ct;
}

void main()
{
int arr[MAX],i,incrmnts[MAX], total_incr;
for(i=0;i<MAX;i++)
{
incrmnts[i]=0;
printf(“Enter value?”);
scanf(“%d”,&arr[i]);
}
total_incr = hash(incrmnts,MAX);
shellsort(arr,MAX,incrmnts,total_incr);
printf(“Sorted array is: “);
for(i=0;i<MAX;i++)
{
printf(“%d\t”,arr[i]);
}
getch();
}

x Close