NonRecursive QuickSort

import java.io.*;
class  NonRecQuickSort
{
static int partition(int a[],int lb,int ub)
{
int down,up,x,temp;
down=lb;
up=ub;
x=a[lb];
while(down<up)
{
while(a[down]<=x&&down<ub)down++;
while(a[up]>x)up–;
if(down<up)
{
temp=a[down];
a[down]=a[up];
a[up]=temp;
}
}
a[lb]=a[up];
a[up]=x;
return up;
}
static void quicksort(int a[])
{

int stack[]=new int[100];
int top=-1,lb,ub, j;
stack[++top]=0;
stack[++top]=a.length-1;
while(top>=0)
{
ub=stack[top--];
lb=stack[top--];
while(lb<ub)
{ j=partition(a,lb,ub);
stack[++top]=j+1;
stack[++top]=ub;
ub=j-1;
}

}
}
public static void main(String args[])throws IOException
{
int a[],n,i;
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
System.out.println(“enter number of elements”);
n=Integer.parseInt(br.readLine());
a=new int[n];
System.out.println(“enter elements”);
for(i=0;i<n;++i)
a[i]=Integer.parseInt(br.readLine());
quicksort(a);
System.out.println(“sorted list”);
for(i=0;i<n;++i)
System.out.print(a[i]+”  “);
System.out.println();
}
}

Randomized QuickSort

import java.io.*;
import java.util.*;
import java.util.Random;
class quickran
{
static int partition(int a[],int l,int r)
{
int i,j,x,t;
i=l;
x=a[l];
while(i<j)
{
while(i<=r&&a[i]<=r)
i++;
while(a[j]>x)
j–;
if(i<j)
{
t=a[i];
a[j]=a[j];
a[j]=t;
}
}

t=a[j];
a[j]=a[l];
a[l]=t;
return j;
}

static void random_quicksort(int a[],int l,int r)
{
int p;
if(l<r)
{    int seed=45;
Random x= new Random() ;
int y =x.newInt();
y=(y+l)%(r-l+1);
int t=a[l];
a[l]=a[y];
a[y]=t;
p=partition(a,l,r);
random_quicksort(a,l,r);
random_quicksort(a,p+1,r);
}
}

public static void main(String arg[])
{
System.out.println(“entrt no of ele”);
Scanner kbd=new Scanner(System.in);
int n=kbd.nextInt();
int a[]=new int [n];
for(int j=0;j<=n-1;j++)
{
System.out.println(“enter ele”+(j+1));

for(int i=0;i<=n-1;i++)
{
System.out.println(“enter ele “+(i+1));
a[i]=kbd.nextInt();
}

random_quicksort(a,0,n-1);
for(int i=0;i<=n-1;i++)
{
System.out.println(a[i]);
}
}
}
}

My_Prim

import java.io.*;

class Prim_code
{
public static void main(String args[])
{
String ip;
//int a[][],b[][],V[],E[],wt[];

int n,minWt;
try
{
InputStreamReader ds= new InputStreamReader(System.in);
BufferedReader br= new BufferedReader(ds);

System.out.println(“\n Enter no. of nodes in matrix”);
n=Integer.parseInt(br.readLine());

//int FMW(int[]);

int b[][]=new int[n][n];
int a[][]=new int[n][n];

System.out.println(“\n Enter weights of edges in graph,enter 0 if vertices disconnected\n\n”);
for(int i=0; i<n; i++)
{
for(int j=i;j<n;j++)
{
System.out.println(“\n Edge joins”+(i+1)+”to”+(j+1)+”with weight:”);
a[i][j]=Integer.parseInt(br.readLine());
a[j][i]=a[i][j];b[i][j]=a[i][j];b[j][i]=a[i][j];
}
}
int V[]=new int[n];
System.out.println(“\n Enter starting node”);
V[0]=Integer.parseInt(br.readLine());

int wt[]=new int[n];
int t=1;
while(t<n)
{//t is index of array V; V is array of vertices in solution

//Wipe out column corresp to node already in V so as to avoid re-inclusion of node
for(int j=0;j<n;j++)
{a[j][V[t-1]]=0;
wt[j]=0;
}
//Cleaning out wt array to avoid prev values clogging

for(int i=0,j=0;i<n;i++)
{    //Checks row corresp. to edge in V & stores weights of all existing edges in array wt

if(a[V[t-1]][i]!=0)
{wt[j++]=a[V[t-1]][i];

}
}
//minWt=FMW(wt[]);

//public static int FMW(int x[])
//{
int min=wt[0];
for(int p=1; p<n; p++)
{if (wt[p]<min)
min=wt[p];
}
//return min;
//}
minWt=min;

for(int i=0;i<n;i++)
{    //Locates node(column) corresp to min wt and adds it to vertice listV
if(a[V[t-1]][i]==minWt)
{V[t]=i;
}
}
t++;
}

//Finding Edges corresp to vertice list
//V[i]->Row no, V[i+1]->Col no
int E[]=new int[n];
for(int i=0;i<n-1;i++)
{    E[i]=b[V[i]][V[(i+1)]];
}

for (int i=0;i<n-1;i++)
{System.out.println(“Edge”+E[i]+”\t joins Vertices”+V[i]+” and”+V[(i+1)]);
}

}//End of try

catch(Exception e)
{
System.out.println(“Check Code”);
}

}//End of main

}//End of class Prim

My_MergeSort

import java.io.*;
class MergeSort
{
int a[],n;
MergeSort(int m)
{
n=m;
a=new int[n];
}

void getElements()throws IOException
{
InputStreamReader ds=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(ds);
for(int i=0;i<n;i++)
{
System.out.println(“Enter elements”);
a[i]=Integer.parseInt(br.readLine());
}
}

void putElements()
{System.out.println(“the sorted elements are”);
for(int i=0;i<n;i++)
System.out.println(a[i]);
}

void mergeSort(int left,int right)
{
int m=0;
if(left<right)
{
m=(left+right)/2;
mergeSort(left,m);
mergeSort(m+1,right);
simpleMerge(left,m-1,right);
}
}

void simpleMerge(int start,int mid,int end)
{
//mid is actually end of 1st array, end is end of 2nd array
int y,j,k,temp[],comp=0,ecomp=0;
y=start;
j=mid;
k=0;
temp=new int[n];
while(y<=mid-1 && j<=end)
{
if(a[y]<a[j])
temp[k++]=a[y++];
else
temp[k++]=a[j++];
ecomp++;
comp=comp+3;
}
while(y<=mid-1)
{
temp[k++]=a[y++];
comp++;
}

while(j<=end)
{
temp[k++]=a[j++];
comp++;
}
for(int w=0;w<k ;w++,comp++)
a[w]=temp[w];

System.out.println(“\n Comparisons made:”+comp+”\n Element comparisons:”+ecomp);
}

}

class MSORT07_20
{
public static void main(String args[])throws IOException
{
InputStreamReader ds=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(ds);
int n;
System.out.println(“Enter no. of elements”);
n=Integer.parseInt(br.readLine());
MergeSort ob=new MergeSort(n);
ob.getElements();
ob.mergeSort(0,n-1);
ob.putElements();
}
}

PatternMatching

/**************************************************************/
/*  Patternmatching Using BruteForce Method
/*************************************************************/
import java.io.*;
class PatternMatch1
{
static boolean brutForce(String t,String p)
{
int i,j;
int m=t.length();
int n=p.length();
for(i=0;i<=m-n;++i)
{
for(j=0;j<n;++j)
if(t.charAt(i+j)!=p.charAt(j))break;
if(j==n)return true;
}
return false;
}
public static void main(String args[])throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String text,pattern;
System.out.println(“Enter Text”);
text=br.readLine();
System.out.println(“Enter Pattern”);
pattern=br.readLine();
boolean flag=brutForce(text,pattern);
if(flag)System.out.println(pattern+” is  a  substring of “+text);
else  System.out.println(pattern +” is not a substring of “+text);
}
}

Kruskal1

/****************************************************************************/
/****************************************************************************/
/*          Prgram to Find Minimum Cost Spanning Tree                           */
/*           using Kruskal’s algorithm                                                            */
/*          Sureshan 09322264001  Office:(022)65752141                          */
/****************************************************************************/
/****************************************************************************/
import java.io.*;
class Edge
{
int  u;
int  v;
int  wt;
}
class Graph
{
Edge e[ ];
int n;
int m;

Graph(int n,int m )
{
this.n=n;
this.m=m;
e=new Edge[m];
}

void createGraph( )throws IOException
{ int i,a,b,wt;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

for(i=0;i<m;++i)
{
System.out.println(“Enter an edge  and its weight”);
a=Integer.parseInt(br.readLine());
b=Integer.parseInt(br.readLine());
wt=Integer.parseInt(br.readLine());
e[i]=new Edge();
e[i].u=a;
e[i].v=b;
e[i].wt=wt;
}
}
void sortEdges( )
{ int i,j;
Edge temp;
for(i=0;i<m-1;++i)
for(j=i+1;j<m;++j)
if(e[i].wt>e[j].wt){
temp=e[i];
e[i]=e[j];
e[j]=temp;
}
}

boolean cycleCheck(int i,int p[ ])
{
int u,v;
u=e[i].u;
v=e[i].v;
while(p[u]>-1)
u=p[u];
while(p[v]>-1)
v=p[v];
if(u!=v)
{
System.out.println(e[i].u +”  “+e[i].v);
p[v]=u;
return true;
}
return false;

}

}
class Kruskal
{
public static void main(String args[ ])throws IOException
{
int n,m,j,i,cost=0;
BufferedReader  br=new BufferedReader(new InputStreamReader(System.in));
System.out.println(“Enter number of nodes &edges”);
n=Integer.parseInt(br.readLine());
m=Integer.parseInt(br.readLine());

Graph g1=new Graph(n,m);

g1.createGraph();
g1.sortEdges();
int parent[ ]=new int[n];
for(i=0;i<n;++i)
parent[i]=-1;

System.out.println(“Edges of minimum cost spanning tree”);

i=0;j=0;
while(i<n-1)
{
if(g1.cycleCheck(j,parent)){
i++;
cost+=g1.e[j].wt;
}
j++;
}
System.out.println(“Cost =”+cost);

}
}

QuickSort-Recursive

import java.io.*;

/* program to sort an array using quicksort – recursive */
import java.util.*;
class QuickSortRec
{

static int partition(int a[],int lb,int ub)
{
int down,up,x,temp;
down=lb;up=ub;
x=a[lb];
while(down <up)
{
while(a[down]<=x && down <ub)
down++;
while(a[up]>x)up–;
if(down<up)
{temp=a[down];
a[down]=a[up];
a[up]=temp;
}
}
a[lb]=a[up];
a[up]=x;
return up;
}
static void rquicksort(int a[],int lb,int ub)
{Random r=new Random();
int j,k;
if(lb<ub){  k=r.nextInt(ub)%(ub-lb+1)+lb;
int temp=a[lb];a[lb]=a[k];a[k]=temp;
System.out.println(“lb=”+lb+”ub=”+ub+”in=”+k);                         j=partition(a,lb,ub);
rquicksort(a,lb,j-1);
rquicksort(a,j+1,ub);
}
}

static void quicksort(int a[],int lb,int ub)
{
int j;
if(lb<ub)
{
System.out.println(“lb=”+lb+” ub=”+ub);
j=partition(a,lb,ub);
quicksort(a,lb,j-1);
quicksort(a,j+1,ub);
}
}
public static void main(String args[])throws IOException
{
int a[],n,i;

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

System.out.println(“Enter number of elements”);

n=Integer.parseInt(br.readLine());

a=new int[n];

System.out.println(“Enter elements”);

for(i=0;i<n;++i)
a[i]=Integer.parseInt(br.readLine());
int b[]=new int[n];
System.arraycopy(a,0,b,0,n);
quicksort(a,0,n-1);

System.out.println(“Array after sorting”);
for(i=0;i<n;++i)
System.out.print(a[i] +”  “);
System.out.println();
rquicksort(b,0,n-1);
System.out.println(“\nArray after sorting”);
for(i=0;i<n;++i)
System.out.print(a[i]+” “);
}
}

Prim1

/****************************************************************************/
/****************************************************************************/
/* Prgram to Minimum Cost Spanning Tree for given weighted Graph  */
/*  using Prim’s Algorithm                                                                         */
/*   Sureshan 09322264001  Office:(022)65752141                                 */
/****************************************************************************/
/****************************************************************************/
import java.io.*;
class Graph
{  final  int INF=1000;
boolean   adj[ ][ ];
int   weight[ ][ ];
int   n;
int   m;

Graph(int n,int m )
{
this.n=n;
this.m=m;
adj=new boolean [n][n];
weight=new int[n][n];
}

void createGraph( )throws IOException
{ int i,j,a,b,wt;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
for(i=0;i<n;++i)
for(j=0;j<n;++j)
if(i==j)
weight[i][j]=0;
else
weight[i][j]=INF;

for(i=1;i<=m;++i)
{
System.out.println(“Enter an edge  and its weight”);
a=Integer.parseInt(br.readLine());
b=Integer.parseInt(br.readLine());
wt=Integer.parseInt(br.readLine());
adj[a][b]=true;
weight[a][b]=wt;

}
}

void prim(int v)
{
int i,j,mindist,root,current=0,cost=0;
int dist[ ]=new int[n];
int nearest[ ]=new int[n];
root=v;
for(i=0;i<n;++i)
{  dist[i]=weight[root][i];
nearest[i]=root;
}
dist[v]=-1;
for(i=1;i<=n-1;++i)
{
mindist=INF;
for(j=0;j<n;++j)
if(dist[j]!=-1 && dist[j]<mindist)
{ mindist=dist[j];
current=j;
}
System.out.println(nearest[current]+”  “+current);
cost+=dist[current];
dist[current]=-1;
for(j=0;j<n;++j)
if(dist[j]!=-1 && weight[current][j]<dist[j])
{dist[j]=weight[current][j];
nearest[j]=current;
}
}
System.out.println(“Cost=”+cost);
}

void printGraph( )
{
int i,j;
System.out.println(“Adjacency Matrix “);
for(i=0;i<n;++i)
{
for(j=0;j<n;++j)
if(adj[i][j])System.out.print(” T  “);
else
System.out.print(” F  “);
System.out.println();
}

System.out.println(“Weight Matrix”);

for(i=0;i<n;++i)
{
for(j=0;j<n;++j)
if(weight[i][j]==INF)System.out.print((char)236+”  “);
else
System.out.print(weight[i][j] +”  “);
System.out.println();
}

}
}
class Prim
{
public static void main(String args[ ])throws IOException
{
int n,m;
BufferedReader  br=new BufferedReader(new InputStreamReader(System.in));
System.out.println(“Enter number of node &edges”);
n=Integer.parseInt(br.readLine());
m=Integer.parseInt(br.readLine());
Graph g1=new Graph(n,m);
g1.createGraph();
g1.printGraph();
System.out.println(“Edges of the requiured Minimal Spanning Tree”);
g1.prim(0);
}
}

NonRecursiveNQueen

/* recursive implementation of n queen problem */

import  java.io.*;
class NonRecursiveNQueen
{  static  int  c=0;
static  boolean  place(int k,int i,int x[])
{
int j;
for(j=1;j<k;++j)
if(x[j]==i || Math.abs(x[j]-i)==Math.abs(j-k))return false;
return true;
}
static void nQueen(int n,int x[])
{
int i,j,k=1;
x[1]=0;
while(k>0)
{
x[k]++;
while(x[k]<=n && !place(k,x[k],x))
x[k]++;

if(x[k]<=n)
if(k ==n)

{
for(j=1;j<=n;++j)
System.out.print(x[j]+” “);
System.out.println();
c++;
}
else  k++;
else
{x[k]=0; k–;}
}

}

public static void main(String args[]) throws IOException
{
int n,k;
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
System.out.println(“enter number of queens”);
n=Integer.parseInt(br.readLine());
int x[]=new int[n+1];
nQueen(n,x);
System.out.println(“Number of Solutions:”+ c);
}
}

Recursive NQueen

/* recursive implementation of n queen problem */

import  java.io.*;
class RecursiveNQueen
{  static  int  c=0;
static  boolean  place(int k,int i,int x[])
{
int j;
for(j=1;j<k;++j)
if(x[j]==i || Math.abs(x[j]-i)==Math.abs(j-k))return false;
return true;
}
static void nQueen(int k,int n,int x[])
{
int i,j;
for(i=1;i<=n;++i)
if(place(k,i,x))
{       x[k]=i;
if(k==n)
{for(j=1;j<=n;++j)
System.out.print(x[j]+” “);
System.out.println();
c++;
}
else
nQueen(k+1,n,x);
}

}

public static void main(String args[]) throws IOException
{
int n,k;
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
System.out.println(“enter number of queens”);
n=Integer.parseInt(br.readLine());
int x[]=new int[n+1];
nQueen(1,n,x);
System.out.println(“Number of Solutions:”+ c);
}
}