programming centre: June 2015

Monday, June 29, 2015

C++ program to implement Merge Sort

/*-------------------------------------------------------------------------------------------------------------

File Name: merge.cpp

Author: sujith

Program: Write a C++ program to implement Merge Sort

Date: 21-04-2015

--------------------------------------------------------------------------------------------------------------*/

#include<iostream>

#include<stdio.h>

using namespace std;

void mergesort(int a[20],int n);

int main()

{

int i,n,a[20];

cout<<"Enter the total number of element\n";

cin>>n;

cout<<"Enter the Elements\n";

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

{

cin>>a[i];

}

cout<<"After sorting\n";

mergesort(a,n);

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

cout<<a[i]<<"\n";

}

void mergesort(int a[20],int n)

{

int aux[20],i,j,k,l1,l2,u1,u2,size;

size=1;

while(size<n)

{

l1=0;

k=0;

while(l1+size<n)

{

l2=l1+size;

u1=l2-1;

u2=(l2+size-1<n)?l2+size-1:n-1;

for(i=l1,j=l2;i<=u1&&j<=u2;k++)

{

if(a[i]<=a[j]){

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

}else{

aux[k]=a[j++];

}

for(;i<=u1;k++){

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

}

for(;j<=u2;k++){

aux[k]=a[j++];

}

l1=u2+1;

}

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

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

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

a[i]=aux[i];

size=size*2;

}

OUTPUT:

[141740@localhost ~]$ g++ merge.cpp

[141740@localhost ~]$ ./a.out

Enter the total number of element

Enter the Elements

11 33 55 22 88

After sorting

Saturday, June 13, 2015

C++ program to implement Quick Sort

/*-------------------------------------------------------------------------------------------------------------

File Name: quick.cpp

Author: sujith

Program: Write a C++ program to implement Quick Sort

Date: 21-04-2015

--------------------------------------------------------------------------------------------------------------*/

#include<iostream>

#include<stdio.h>

using namespace std;

void quicksort(int a[20],int low,int high);

int partition(int a[20],int low,int high);

int main()

{

int i,n,a[20];

cout<<"Enter the total number of element\n";

cin>>n;

cout<<"Enter the Elements\n";

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

{

cin>>a[i];

}

cout<<"After sorting\n";

quicksort(a,0,n-1);

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

cout<<a[i]<<"\n";

}

void quicksort(int a[],int low,int high)

{

int keypos;

if(low<high)

{

keypos=partition(a,low,high);

quicksort(a,low,keypos-1);

quicksort(a,keypos+1,high);

}

int partition(int a[20],int low,int high)

{

int i,j,temp,flag,key;

key=a[low];

i=low+1;

j=high;

flag=1;

while(flag)

{

while(key>a[i]&&i<high){

i++;

}

while(key<a[j]){

j--;

}

if(i<j){

temp=a[i];

a[i]=a[j];

a[j]=temp;

}else{

flag=0;

}

temp=a[low];

a[low]=a[j];

a[j]=temp;

return j;

}

OUTPUT:

[141740@localhost ~]$ g++ quick.cpp

[141740@localhost ~]$ ./a.out

Enter the total number of element

Enter the Elements

33 22 88 44 66

After sorting

[141740@localhost ~]$ g++ quick.cpp

[141740@localhost ~]$ ./a.out

Enter the total number of element

Enter the Elements

22 5 3 9 7 1

After sorting

[141740@localhost ~]$

C++ program to implement selection Sort

/*-------------------------------------------------------------------------------------------------------------

File Name: selection.cpp

Author: sujith

Program: Write a C++ program to implement selection Sort

Date: 23-04-2015

--------------------------------------------------------------------------------------------------------------*/

#include<iostream>

#include<stdio.h>

using namespace std;

void selectionsort(int a[],int n);

int main()

{

int i,n,a[20];

cout<<"Enter the total number of element\n";

cin>>n;

cout<<"Enter the Elements\n";

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

{

cin>>a[i];

}

cout<<"After sorting\n";

selectionsort(a,n);

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

cout<<a[i]<<"\n";

}

void selectionsort(int a[],int n)

{

int i,j,max,index;

for(i=n-1;i>=0;i--){

max=a[0];

index=0;

for(j=1;j<=i;j++){

if(a[j]>max){

max=a[j];

index=j;

}

a[index]=a[i];

a[i]=max;

}

OUTPUT:

[141740@localhost ~]$ g++ selection.cpp

[141740@localhost ~]$ ./a.out

Enter the total number of element

Enter the Elements

15 2 4 89 66

After sorting

[141740@localhost ~]$ g++ selection.cpp

[141740@localhost ~]$ ./a.out

Enter the total number of element

Enter the Elements

1 5 4 99 6 3

After sorting

[141740@localhost ~]$

C++ program to implement insertion Sort

/*-------------------------------------------------------------------------------------------------------------

File Name: insertion.cpp

Author: sujith

Program: Write a C++ program to implement insertion Sort

Date: 23-04-2015

--------------------------------------------------------------------------------------------------------------*/

#include<iostream>

#include<stdio.h>

using namespace std;

void insertionsort(int a[],int n);

int main()

{

int i,n,a[20];

cout<<"Enter the total number of element\n";

cin>>n;

cout<<"Enter the Elements\n";

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

{

cin>>a[i];

}

cout<<"After sorting\n";

insertionsort(a,n);

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

cout<<a[i]<<"\n";

}

void insertionsort(int a[],int n)

{

int i,j,key;

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

{

key=a[i];

for(j=i-1;j>=0&&key<a[j];j--){

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

}

a[j+1]=key;

}

OUTPUT:

[141740@localhost ~]$ g++ insertion.cpp

[141740@localhost ~]$ ./a.out

Enter the total number of element

Enter the Elements

5 6 3 7 9

After sorting

[141740@localhost ~]$ g++ insertion.cpp

[141740@localhost ~]$ ./a.out

Enter the total number of element

Enter the Elements

56 8 2 7 4

After sorting

[141740@localhost ~]$

C++ program to implement Bubble Sort

/*-------------------------------------------------------------------------------------------------------------

File Name: bubblesort.cpp

Author: sujith

Program: Write a C++ program to implement Bubble Sort

Date: 23-04-2015

--------------------------------------------------------------------------------------------------------------*/

#include<iostream>

#include<stdio.h>

using namespace std;

int main()

{

int n,i,j,a[20],temp;

cout<<"Enter the total number of element\n";

cin>>n;

cout<<"Enter the elements\n";

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

{

cin>>a[i];

}

cout<<"sorted element is\n";

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

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

{

if(a[j]>a[j+1]){

temp=a[j];

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

a[j+1]=temp;

}

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

cout<<a[i]<<"\n";

}

OUTPUT:

[141740@localhost ~]$ g++ bubblesort.cpp

[141740@localhost ~]$ ./a.out

Enter the total number of element

Enter the elements

56 23 5 4 9

sorted element is

[141740@localhost ~]$ g++ bubblesort.cpp

[141740@localhost ~]$ ./a.out

Enter the total number of element

Enter the elements

5 3 2 9 7

sorted element is

[141740@localhost ~]$

Menu Driven C++ program to implement Linear search and Binary search

/*-------------------------------------------------------------------------------------------------------------

File Name: 17 linearandbinary.cpp

Author: sujith

Reg No: 141740

Program: Write Menu Driven C++ program to implement the following

i. Linear search

ii. Binary search

Date: 23-04-2015

--------------------------------------------------------------------------------------------------------------*/

#include<iostream>

#include<stdio.h>

using namespace std;

int linearsearch(int a[20],int key,int n);

int binarysearch(int a[20],int key,int n);

int main()

{

int a[20],k,n,ch,ans,i;

cout<<"Enter the total number of elements\n";

cin>>n;

while(1){

cout<<"\nMenu\n";

cout<<"1.linear search\n";

cout<<"2.binary search\n";

cout<<"3.exit\n";

cout<<"Enter your choice\n";

cin>>ch;

switch(ch){

case 1:

cout<<"Enter the elements\n";

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

cin>>a[i];

}

cout<<"Enter the key elememts\n";

cin>>k;

ans=linearsearch(a,k,n);

if(ans!=-1)

cout<<"element\t"<<k<<"\tis found\n";

else

cout<<"Element\t"<<k<<"\tis not found\n";

break;

case 2:

cout<<"Enter the elements\n";

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

cin>>a[i];

}

cout<<"Enter the key elememts\n";

cin>>k;

ans=binarysearch(a,k,n);

if(ans!=-1)

cout<<"element\t"<<k<<"\tis found\n";

else

cout<<"Element\t"<<k<<"\tnot found\n";

break;

case 3:

exit(0);

default:

cout<<"Invalid entry\n";

}

int linearsearch(int a[20],int key,int n)

{

int i;

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

if(key==a[i])

return i;

}

return -1;

}

int binarysearch(int a[20],int key,int n)

{

int high,low,mid;

low=0;

high=n-1;

while(low<=high){

mid=(low+high)/2;

if(a[mid]==key)

return mid;

else if(a[mid]<key)

low=mid+1;

else

high=mid-1;

}

return -1;

}

OUTPUT:

[141740@localhost ~]$ g++ linearandbinary.cpp

[141740@localhost ~]$ ./a.out

Enter the total number of elements

1.linear search

2.binary search

Enter your choice

Enter the elements

1 5 6 7 4

Enter the key elememts

element 7 is found

1.linear search

2.binary search

3.exit

Enter your choice

Enter the elements

55 66 77 88 99

Enter the key elememts

100

Element 100 is not found

1.linear search

2.binary search

3.exit

Enter your choice

Enter the elements

15 55 66 44 22

Enter the key elememts

element 55 is found

1.linear search

2.binary search

3.exit

Enter your choice

Enter the elements

55 66 45 56 23

Enter the key elememts

100

Element 100 not found

1.linear search

2.binary search

3.exit

Enter your choice

[141740@localhost ~]$