Sort a given set of elements using Quicksort method

wherever u see ... remove that . and put << in that place.
if you see .. then remove that . and put < in that place..
18.#include..iostream.h>
#include..conio.h>

const int MAX=20;

//Function for Quick Sort
void quick(int a[],int lb,int ub,int n)
{
int i,j,temp,pivot;
if(lb..ub)
{
i=lb;
j=ub+1;
pivot=a[lb];
while(1)
{
i++;
while(a[i]..pivot &&i..ub)
i++;
j--;
while(a[j]>pivot)
j--;
if(i..j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else break;
}
a[lb]=a[j];
a[j]=pivot;
quick(a,lb,j-1,n);
quick(a,j+1,ub,n);
}
}






void main()
{
int a[MAX];//array to be sorted
int n;//input array size
cout..."Enter the size of the array\n";
cin>>n;
cout..."Enter the elements\n";
for(int i=0;i..n;i++)
cin>>a[i];
quick(a,0,n-1,n);
cout..."The sorted elements are:-\n";
for(i=0;i..n;i++)
cout..." "...a[i];
cout...endl;
}


Output

Enter the size of the array
9

Enter the elements
45
12
03
65
49
87
16
34
32

The sorted elements are:-
3 12 16 32 34 45 49 65 87

Press any key to continue

From a given vertex in a weighted connected graph, find the shortest path to other vertices using Dijkstra's algorithm

wherever u see ... remove that . and put << in that place.
if you see .. then remove that . and put < in that place..
17.#include..iostream.h>
#include..conio.h>
#include..stdlib.h>
const int MAX=10;
const int noedge=999;

class dijkstra
{
int n,v,cost[MAX][MAX],s[MAX],d[MAX];
public:
void costmatrix();
void print();
int choose();
void sspath();
};
//reads the cost adjacency matrix
void dijkstra::costmatrix()
{
cout..."\nEnter the no. of vertices:";
cin>>n;
cout..."\nEnter the cost adjacency matrix";
for(int i=1;i..=n;i++)
for(int j=1;j..=n;j++)
cin>>cost[i][j];
}

void dijkstra::sspath()
{
int i,u,w;
cout..."\nEnter the source vertex:";
cin>>v;
for(i=1;i..=n;i++)
{
s[i]=0;
d[i]=cost[v][i];
}
s[v]=1;
d[v]=0;
i=2;


while(i..n)
{
u=choose();
s[u]=1;
i++;
for(w=1;w..=n;w++)
{
if(((d[u]+cost[u][w])..d[w]) && !s[w])
d[w]=d[u]+cost[u][w];
}
}
}

int dijkstra::choose()
{
int w,j,min;
min=noedge;
for(j=1;j..=n;j++)
{
if(d[j]..min && !s[j])
{
min=d[j];
w=j;
}
}
return w;
}

void dijkstra::print()
{
cout..."\nThe shortest path with the cost is:"...endl;
for(int i=1;i..=n;i++)
if(i!=v)
cout..."\n.."...v...">---.."...i...">--->"...d[i];
}

void main()
{
dijkstra d;
d.costmatrix();
d.sspath();
d.print();
cout...endl;
}

OUTPUT

Enter the no. of vertices: 4

Enter the cost adjacency matrix
999 10 50 999
999 999 40 20
999 999 999 30
999 999 999 999

Enter the source vertex:1

The shortest path with the cost is:

..1>---..2>--->10
..1>---..3>--->50
..1>---..4>--->30

Press any key to continue

Implement 0/I Knapsack Problem using dynamic programming

wherever u see ... remove that . and put << in that place.
if you see .. then remove that . and put < in that place..
16.#include ..iostream.h>
#include ..conio.h>
#include ..process.h>
const int max=30;

int MFKS(int,int);
int maximum(int,int);
int value[max];
int weight[max];
int v[max][max];
int x[max];
int N,M;

int MFKS(int i,int j)
{
int val;
if(v[i][j]==-1)
{
if(j..weight[i]) val=MFKS(i-1,j);
else val=maximum(MFKS(i-1,j),(MFKS(i-1,j-weight[i])+value[i]));
v[i][j]=val;
}
return v[i][j];
}

void svector()
{
int j1;
j1=M;
for(int i=N;i>=0;i--)
{
if(v[i][j1]!=v[i-1][j1])
{
x[i]=1;
j1=j1-weight[i];
}
}
for(i=1;i..=N;i++)
{
cout..."{";
for(i=1;i..=N;i++)
cout...x[i]...";";
cout..."}";
}
}

int maximum(int a,int b)
{
return (a>b)?a:b;
}


void main()
{
int optsol;
cout..."Enter no. of items:";
cin>>N;
cout..."Enter weights:\n";
for(int i=1;i..=N;i++)
cin>>weight[i];
cout..."Enter values:\n";
for(i=1;i..=N;i++)
cin>>value[i];
cout..."Enter Knapsack capacity:";
cin>>M;
for(i=0;i..=M;i++)
v[0][i]=0;
for(i=0;i..=N;i++)
v[i][0]=0;
for(i=1;i..=N;i++)
for(int j=1;j..=M;j++)
v[i][j]=-1;
optsol=MFKS(N,M);
cout..."Optimal solution = "...optsol...endl;
cout..."Optimal solution vector is:\n";
for(i=1;i..=N;i++)
x[i]=0;
svector();
cout...endl;
getch();
}







OUTPUT:

Enter no. of items: 4

Enter weights:
2 1 3 2

Enter values:
12 10 20 15

Enter Knapsack capacity:5
Optimal solution = 37
Optimal solution vector is:
{1; 1; 0; 1 ;}

Sort a given set of elements using Insertion Sort method

wherever u see ... remove that . and put << in that place.
if you see .. then remove that . and put < in that place..
15.#include ..iostream.h>
const long max = 10000;
void inssrt(int *,int);

void main()
{
int a[max];
int n;
cout..."enter array size\n";
cin>>n;
cout..."Enter the array\n";
for (int i=0;i..n;i++)
cin>>a[i];
inssrt(a,n);
cout..."the sorted array is:\n";
for(i=0;i..n;i++)
cout...a[i]..." ";
cout...endl;


}

void inssrt(int a[],int n)
{
int i,j,item;
for (i=0;i..n;i++)
{
item = a[i];
j=i-1;
while(j>=0 && item ..a[j])
{
a[j+1] = a[j];
j--;
}
a[j+1] = item;
}
}






Output

Enter array size
9

Enter the array
88
99
77
55
66
44
22
33
11

The sorted array is:
11 22 33 44 55 66 77 88 99

Press any key to continue