SORTING PROGRAMS (INSERTION SORT,MARGE SORT, QUICK SORT, SHELL SORT}

SORTING PROGRAMS (INSERTION SORT,MARGE SORT, QUICK SORT, SHELL SORT}

Posted on October 23, 2015

• 
  
• WAP to sort array of integers using insertion sort.

#include<iostream.h>

#include<conio.h>

void main(){

clrscr();

inti,k,j,n,t,a[20];

cout<<“Enter number of elements:”;

cin>>n;

cout<<“Enter unsorted elements:\n”;

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

cin>>a[i];

}

for(k=1;k<n;k++){

t=a[k];

j=k-1;

while((j>=0)&&(t<a[j]))

{

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

j–;

}

a[j+1]=t;

}

cout<<“Elements after sorting\n”;

for(j=0;j<n;j++){

cout<<a[j]<<” “;

}

getch();

}

2. WAP to sort array of integers using merge sort.

#include<iostream.h>

#include<conio.h>

voidmergesort(int *,int,int);

void merge(int *,int,int,int);

int a[20],i,n,b[20];

void main()

{

clrscr();

cout<<“Enter no of elements:”;

cin>> n;

cout<<“Enter elements:”;

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

cin>> a[i];

mergesort(a,0,n-1);

cout<<“\nNumbers after sort:”;

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

cout<< a[i] << ” “;

getch();

}

voidmergesort(int a[],inti,int j)

{

int mid;

if(i<j)

{

mid=(i+j)/2;

mergesort(a,i,mid);

mergesort(a,mid+1,j);

merge(a,i,mid,j);

}

}

void merge(int a[],intlow,int mid ,int high)

{

inth,i,j,k;

h=low;

i=low;

j=mid+1;

while(h<=mid && j<=high)

{

if(a[h]<=a[j])

b[i]=a[h++];

else

b[i]=a[j++];

i++;

}

if( h > mid)

for(k=j;k<=high;k++)

b[i++]=a[k];

else

for(k=h;k<=mid;k++)

b[i++]=a[k];

cout<<“\n”;

for(k=low;k<=high;k++)

{  a[k]=b[k];

cout<< a[k] <<” “;

}

}

3. WAP to sort array of integers using quick sort.

#include<iostream.h>

#include<conio.h>

int a[10],l,u,i,j;

void quick(int *,int,int);

void main()

{

clrscr();

cout<<“Enter 10 elements:\n”;

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

cin>> a[i];

l=0;

u=9;

quick(a,l,u);

cout<<“\nSorted elements:”;

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

cout<< a[i] << ” “;

getch();

}

void quick(int a[],intl,int u)

{

intp,temp;

if(l<u)

{

p=a[l];

i=l;

j=u;

while(i<j)

{

while(a[i] <= p && i<j )

i++;

while(a[j]>p && i<=j )

j–;

if(i<=j)

{

temp=a[i];

a[i]=a[j];

a[j]=temp;}

}

temp=a[j];

a[j]=a[l];

a[l]=temp;

cout<<“\n”;

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

cout<<a[i]<<” “;

quick(a,l,j-1);

quick(a,j+1,u);

}}

4. WAP of shell sort.

#include<iostream.h>

#include<conio.h>

void read(int a[10],int n)

{

cout<<“Enter elements:\n”;

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

cin>>a[i];

}

void display(int a[10],int n)

{

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

cout<<a[i]<<“\t”;

}

voidshellsort(int a[10],int n)

{

int gap=n/2;

do

{

int swap;

do

{

swap=0;

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

if(a[i]>a[i+gap])

{

int t=a[i];

a[i]=a[i+gap];

a[i+gap]=t;

swap=1;

}

}

while(swap);

}

while(gap=gap/2);

}

void main()

{

int a[10];

int n;

clrscr();

cout<<“Enter number of elements:”;

cin>>n;

read(a,n);

cout<<“Before sorting\n”;

display(a,n);

shellsort(a,n);

cout<<“\nAfter sorting\n”;

display(a,n);

getch();

}