Sem3 DSF: File Handling

/* Program to demonstrates Read and write bytes */

import java.io.*;

public class ReadWriteBytes
{
static final int LINELENGTH = 80;
public static void main(String arg[]) throws IOException
{
byte [] name = new byte[LINELENGTH];
byte [] number = new byte[LINELENGTH];

FileOutputStream fos = new FileOutputStream(“phone.dat”);
while(true)
{
System.out.println(“Enter Name (enter ‘exit’ to quit): “);
readLine(name);
if(“exit”.equalsIgnoreCase(new String(name,0,4)))
break;
for(int i = 0;name[i] != 13; i++)
{
fos.write(name[i]);
}
fos.write(‘.’);
fos.write(‘.’);
fos.write(‘.’);

System.out.println(“Enter Number : “);
readLine(number);
for( int i = 0; number[i] != 13; i++){
fos.write(number[i]);
}
fos.write(‘\n’);
}
fos.close();
FileInputStream fis = new FileInputStream(“phone.dat”);
int i;
System.out.println(“\n The Telephone Directory:\n”);
do
{
i = fis.read();
if( i != -1 ) System.out.print((char)i);
}while( i != -1);
fis.close();
}

private static void readLine(byte [] line) throws IOException
{
int i = 0, b = 0;
while(i < LINELENGTH – 1 && (b = System.in.read()) != ‘\n’)
{
line[i++] = (byte)b;
}
}
}

Sem3 DSF: Infix to Postfix

import java.io.*;

class Stack

{ char items[]=new char[10];

int top;

Stack()

{ top=-1;

}

void push (char item)

{ if (top==9)

System.out.println(“Stack overflow”);

else

items[++top]=item;

}

int isempty()

{

if (top<0)

return 1;

else

return 0;

}

char pop()

{ if (isempty()==1)

{ System.out.println(“Stack underflow”);

return 0;

}

else

return (items[top--]);

}

}

class Functions

{void postfix(char infix[],char post[])

{ int position,und=1;

int outpos=0;

char topsymb=’+';

char symb;

Stack opstk=new Stack();

opstk.top=-1;

for(position =0;(symb=infix[position])!=”;position++)

{ if(isoperand(symb))

post[outpos++]=symb;

else

{ if (opstk.isempty()==1)

und=1;

else

{ und=0;

topsymb=opstk.pop();

}

while(und==0 && prcd(topsymb,symb)==1)

{ post[outpos++]=topsymb;

if (opstk.isempty()==1)

und=1;

else

{ und=0;

topsymb=opstk.pop();

}

}

if(und==0)

opstk.push(topsymb);

if(und==1||(symb!=’)'))

opstk.push(symb);

else

topsymb=opstk.pop();

}

}

while(opstk.isempty()==0)

post[outpos++]=opstk.pop();

post[outpos]=”;

}

int prcd(char topsymb,char symb)

{ if(topsymb==’(‘)

return 0;

if(symb==’(‘)

return 0;

if(symb==’)')

return 1;

if (topsymb==’$'&&symb==’$')

return 0;

if (topsymb==’$'&&symb!=’$')

return 1;

if (topsymb!=’$'&&symb==’$')

return 0;

if((topsymb==’*'||topsymb==’/')&&(symb!=’$'))

return 1;

if((topsymb== ‘+’||topsymb==’-')&&(symb==’-'||symb==’+'))

return 1;

if((topsymb== ‘+’||topsymb==’-')&&(symb==’*'||symb==’/'))

return 0;

return 1;

}

boolean isoperand(char symb)

{

if(symb>=’0′&& symb<=’9′)

return true;

else

return false;

}

}

class InToPost

{

public static void main(String args[])

{

Functions f=new Functions();

char infix[]=new char[80];

char post[]=new char[80];

int pos=0;char c;

DataInputStream in=new DataInputStream(System.in);

System.out.println(“\nEnter an expression is infix form : “);

try

{

do

{

c=(char)in.read();

infix[pos++]=c;

}while(c!=’\n’);

}

catch(Exception e)

{ System.out.println(“I/O Error”);

}

infix[--pos]=”;

System.out.println(“The original infix expression is : “);

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

System.out.print(infix[i]);

f.postfix(infix,post);

System.out.println(“\nThe postfix expression is : “);

for (int i=0;post[i]!=”;i++)

System.out.println(post[i]);

}

}

Sem3 DSF: Graph Implementation

import java.io.*;
import java.util.*;

class Stack
{
int stk[]=new int[10];
int top;
Stack()
{
top=-1;
}
void push (int item)
{
if (top==9)
System.out.println(“Stack overflow”);
else
stk[++top]=item;
}/*end push*/

boolean isempty()
{
if (top<0)
return true;
else
return false;
}/*end isempty*/

int pop()
{
if (isempty())
{
System.out.println(“Stack underflow”);
return 0;
}
else
return (stk[top--]);
}/*end pop*/

void stacktop()
{
if(isempty())
System.out.println(“Stack underflow “);
else
System.out.println(“Stack top is “+(stk[top]));
}/*end stacktop*/

void display()
{
System.out.println(“Stack–>”);
for(int i=0;i<=top;i++)
System.out.println(stk[i]);
}/*end display*/
}

class Graph
{
int MAXSIZE=51;
int adj[][]=new int[MAXSIZE][MAXSIZE];
int visited[]=new int [MAXSIZE];
Stack s=new Stack();
/*Function  for Depth-First-Search    */

void createGraph()
{
int n,i,j,parent,adj_parent,initial_node;
int  ans=0,ans1=0;

System.out.print(“\nEnter total number elements in a Undirected Graph :”);
n=getNumber();
for ( i=1;i<=n;i++)
for( j=1;j<=n;j++)
adj[i][j]=0;

/*All graph nodes are unvisited, hence assigned zero to visited field of each node */
for (int c=1;c<=50;c++)
visited[c]=0;
System.out.println(“\nEnter graph structure for BFS  “);

do
{
System.out.print(“\nEnter parent node :”);
parent=getNumber();
do
{
System.out.print(“\nEnter adjacent node for node “+parent+ ” : “);
adj_parent=getNumber();
adj[parent][adj_parent]=1;
adj[adj_parent][parent]=1;
System.out.print(“\nContinue to add adjacent node for “+parent+”(1/0)?”);
ans1= getNumber();
} while (ans1==1);
System.out.print(“\nContinue to add graph node?”);
ans= getNumber();
}while (ans ==1);

System.out.print(“\nAdjacency matrix for your graph is :\n”);
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
System.out.print(” “+adj[i][j]);
System.out.print(“\n”);
}

System.out.println(“\nYour Undirected Graph is :”);
for (i=1;i<=n;i++)
{
System.out.print(“\nVertex “+i+”is connected to : “);
for (j=1;j<=n;j++)
{
if (adj[i][j]==1)
System.out.print(” “+j);
}
}
System.out.println(“\nEnter the initial node for BFS traversal:”);
initial_node=getNumber();
DFS (initial_node, n);
}

void DFS (int initial_node,int n)
{
int u,i;
s.top = -1;
s.push(initial_node);
System.out.println(“\nDFS traversal for given graph is : “);
while(!s.isempty())
{
u=s.pop();
if(visited[u]==0)
{
System.out.print(“\n”+u);
visited[u]=1;
}
for (i=1;i<=n;i++)
{
if((adj[u][i]==1) && (visited[i]==0))
{
s.push(u);
visited[i]=1;
System.out.print(” “+i);
u = i;
}
}
}
}/*  end of DFS function  */

int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println(“I/O Error”);
}
return ne;
}
}

class Graph_DFS
{
public static void main(String args[])
{
Graph g=new Graph();
g.createGraph();
}         /*  end of program */
}

/*
Sample Input and Output :

Enter total number elements in a Undirected Graph :9

Enter graph structure for BFS

Enter parent node :1

Enter adjacent node for node 1 : 2

Continue to add adjacent node for 1(1/0)?1

Enter adjacent node for node 1 : 3

Continue to add adjacent node for 1(1/0)?0

Continue to add graph node?1

Enter parent node :2

Enter adjacent node for node 2 : 4

Continue to add adjacent node for 2(1/0)?1

Enter adjacent node for node 2 : 5

Continue to add adjacent node for 2(1/0)?0

Continue to add graph node?1

Enter parent node :3

Enter adjacent node for node 3 : 5

Continue to add adjacent node for 3(1/0)?0

Continue to add graph node?1

Enter parent node :4

Enter adjacent node for node 4 : 6

Continue to add adjacent node for 4(1/0)?1

Enter adjacent node for node 4 : 7

Continue to add adjacent node for 4(1/0)?0

Continue to add graph node?1

Enter parent node :5

Enter adjacent node for node 5 : 8

Continue to add adjacent node for 5(1/0)?0

Continue to add graph node?1

Enter parent node :6

Enter adjacent node for node 6 : 9

Continue to add adjacent node for 6(1/0)?0

Continue to add graph node?0

Adjacency matrix for your graph is :
0 1 1 0 0 0 0 0 0
1 0 0 1 1 0 0 0 0
1 0 0 0 1 0 0 0 0
0 1 0 0 0 1 1 0 0
0 1 1 0 0 0 0 1 0
0 0 0 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0

Your Undirected Graph is :

Vertex 1is connected to :  2 3
Vertex 2is connected to :  1 4 5
Vertex 3is connected to :  1 5
Vertex 4is connected to :  2 6 7
Vertex 5is connected to :  2 3 8
Vertex 6is connected to :  4 9
Vertex 7is connected to :  4
Vertex 8is connected to :  5
Vertex 9is connected to :  6
Enter the initial node for BFS traversal:
1

DFS traversal for given graph is :

1 2 4 6 9 7 5 8 3
*/

Sem3 DSF: Binary Tree traversal

/*Binary search tree traversal using dynamic node representation*/
import java.io.*;
import java.util.*;

class Nodetype
{
int info;
Nodetype left;
Nodetype right;
Nodetype(int i)
{
info=i;
left=null;
right=null;
}
}

class Functions
{

Nodetype maketree(int x)
{
Nodetype node=new Nodetype(x);
return(node);
}/*end maketree*/

void setleft(Nodetype p,int x)
{
if(p==null)
System.out.println(“\nInvalid insertion”);
else
if(p.left!=null)
System.out.println(“\nInvalid insertion”);
else p.left=maketree(x);
}/*end setleft*/

void setright(Nodetype p,int x)
{
if(p==null)
System.out.println(“\nInvalid insertion”);
else
if(p.right!=null)
System.out.println(“\nInvalid insertion”);
else
p.right=maketree(x);
}/*end setright*/

void intrav(Nodetype ptree)
{
if(ptree!=null)
{
intrav(ptree.left);
System.out.print(ptree.info+” “);
intrav(ptree.right);
}
}/*end intrav*/

void pretrav(Nodetype ptree)
{
if(ptree!=null)
{
System.out.print(ptree.info+” “);
pretrav(ptree.left);
pretrav(ptree.right);
}
}/*end pretrav*/

void posttrav(Nodetype ptree)
{
if(ptree!=null)
{
posttrav(ptree.left);
posttrav(ptree.right);
System.out.print(ptree.info+” “);
}
}

void create()
{
Nodetype ptree,p,q;
int n,number=0,i;
System.out.print(“\nEnter number of nodes : “);
n=getNumber();
System.out.println(“\nEnter info “+n+” nodes :”);
number=getNumber();
ptree=maketree(number);
for(i=1;i<n;i++)
{
number=getNumber();
p=q=ptree;
while(q!=null&&number!=p.info)
{
p=q;
if(number<p.info)
q=p.left;
else
q=p.right;
}
if(number==p.info)
System.out.println(“Sorry !…..”+number+”is a duplicate\n”);
else
if(number<p.info)
setleft(p,number);
else
setright(p,number);
}
System.out.println(“\nInorder   : “);
intrav(ptree);
System.out.println(“\nPreorder  : “);
pretrav(ptree);
System.out.println(“\nPostorder : “);
posttrav(ptree);
}

int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println(“I/O Error”);
}
return ne;
}

}

class BSTTrav
{
public static void main(String arg[])
{
Functions f=new Functions();
f.create();

}/*end main*/
}

/*
Enter number of nodes : 4

Enter info 4 nodes :
1
2
3
4

Inorder   :
1 2 3 4
Preorder  :
1 2 3 4
Postorder :
4 3 2 1 Press any key to continue . . .
*/

Sem3 DSF: Linked List Implementation

class Nodetype
{
int info,next;
Nodetype(int i,int n)
{
info=i;
next=n;
}
}

class Operations
{

int maxnodes=10;
Nodetype node[]=new Nodetype[maxnodes];

int avail;
int list=-1;

void createlist()
{
/*link all available nodes together*/

int i;
avail=0;
for(i=0;i<maxnodes-1;i++)
node[i]=new Nodetype(0,i+1);
node[maxnodes-1]=new Nodetype(0,-1);
}

int getnode()
{
/*obtain a node from available list and return its index */
int p;
if(avail==-1)
{
System.out.println(“\nEmpty Linked List”);
}
p=avail;
avail=node[avail].next;
return(p);
}/*end getnode*/

void freenode(int p)
{
/*accept index of a node and return that node to the available list*/
node[p].next=avail;
node[p].info=0;
avail=p;
}/*end freenode*/

void display()
{
/*display all elements of linked list*/
int i;
int temp;
if(list==-1)
System.out.println(“\nEmpty linked list”);
else
{
temp=list;
//System.out.println(“\n”+temp);
System.out.println();

while(temp!=-1)
{
System.out.print(“–>|”+node[temp].info+”|”+node[temp].next+”|”);
temp=node[temp].next;
}
}
}/*end display*/

void insertbeg(int x)
{
/*insert new node at the beginning of linked list*/
int q;
q=getnode();
node[q].info=x;
node[q].next=list;
list=q;
display();
}/*end insertbeg*/

void deletebeg()
{
/*delete a node from the beginning of linked list*/
int p,x;
p=list;
if(p==-1)
System.out.println(“\nEmpty Linked List”);
else
{
x=node[p].info;

list=node[p].next;
System.out.print(“\nThe element deleted is “+x);
freenode(p);
}
display();
}/*end deletebeg*/

void insertend(int x)
{
/*insert new node at the end of linked list*/
int q,temp;
q=getnode();
node[q].info=x;
node[q].next=-1;
temp=list;
if(temp==-1)
{
list=q;
}
else
{
while(node[temp].next!=-1)
temp=node[temp].next;
node[temp].next=q;
}
display();
}/*end insertend*/

void deleteend()
{
/*delete a node from the end of linked list*/
int p,x,temp=-1;
p=list;
if(p==-1)
System.out.println(“\nEmpty Linked List”);
else
{
while(node[p].next!=-1)
{
temp=p;
p=node[p].next;
}
x=node[p].info;
node[temp].next=-1;
System.out.print(“\nThe element deleted is “+x);
freenode(p);
}
display();
}/*delete end*/

void insloc(int p,int x)
{
/*insert new node at specified location*/
int t,i,q,temp;
temp=list;
for(i=0;i<(p-2);i++)
{
if(temp==-1)
break;
temp=node[temp].next;

}
if(temp!=-1)
{
q=getnode();
node[q].info=x;
node[q].next=node[temp].next;
node[temp].next=q;
}
display();
}/*end insertloc*/

void delloc(int p)
{
/*delete a node from specified location*/
int t=-1,i,q,temp;
temp=list;
if(p==1)
list=node[list].next;
for(i=0;i<p-1;i++)
{
if(node[temp].next==-1)
{
System.out.print(“\nThere are less than “+p+” elements in list “);
break;
}
t=temp;
temp=node[temp].next;
}
if(i==p-1)
{
System.out.print(“\nThe element deleted is “+node[temp].info);
node[t].next=node[temp].next;
freenode(temp);
}
display();
}/*end deleteloc*/

void search(int x)
{
/*search an element in linked list and return its location*/
int i=1,q,p;
if(list==-1)
System.out.println(“\nList is empty”);
else
{
q=list;
do
{
if(node[q].info==x)
{
System.out.println(“\nElement found at location “+i);
break;
}
i++;
q=node[q].next;
}
while(q!=-1);
if(q==-1)
System.out.println(“\nElement not found”);
}
}/*end search*/

}

class StaticLL
{
public static void main(String args[])
{

int ch,p,info,x;
char ans=’y';
Operations L =new Operations();
L.createlist();
System.out.print(“\nInsert 55,50,40,90 in the begining “);
L.insertbeg(55);
L.insertbeg(50);
L.insertbeg(40);
L.insertbeg(90);

System.out.print(“\n\nDelete 3 items from the beginning”);
L.deletebeg();
L.deletebeg();
L.deletebeg();

System.out.print(“\n\nInsert 67,22,11,57 in the end “);
L.insertend(67);
L.insertend(22);
L.insertend(11);
L.insertend(57);

System.out.print(“\n\nDelete 2 items from the end”);
L.deleteend();
L.deleteend();

System.out.print(“\n\nInsert 100 at location 2″);
L.insloc(2,100);

System.out.print(“\n\nInsert 80 at location 4″);
L.insloc(4,80);

System.out.print(“\n\nDelete item present at location 2″);
L.delloc(2);

System.out.print(“\n\nDelete item present at location 10″);
L.delloc(10);

System.out.print(“\n\nSearch ’1′ in the list”);
L.search(1);

}
}

/*

Insert 55,50,40,90 in the begining
–>|55|-1|
–>|50|0|–>|55|-1|
–>|40|1|–>|50|0|–>|55|-1|
–>|90|2|–>|40|1|–>|50|0|–>|55|-1|

Delete 3 items from the beginning
The element deleted is 90
–>|40|1|–>|50|0|–>|55|-1|
The element deleted is 40
–>|50|0|–>|55|-1|
The element deleted is 50
–>|55|-1|

Insert 67,22,11,57 in the end
–>|55|1|–>|67|-1|
–>|55|1|–>|67|2|–>|22|-1|
–>|55|1|–>|67|2|–>|22|3|–>|11|-1|
–>|55|1|–>|67|2|–>|22|3|–>|11|4|–>|57|-1|

Delete 2 items from the end
The element deleted is 57
–>|55|1|–>|67|2|–>|22|3|–>|11|-1|
The element deleted is 11
–>|55|1|–>|67|2|–>|22|-1|

Insert 100 at location 2
–>|55|3|–>|100|1|–>|67|2|–>|22|-1|

Insert 80 at location 4
–>|55|3|–>|100|1|–>|67|4|–>|80|2|–>|22|-1|

Delete item present at location 2
The element deleted is 100
–>|55|1|–>|67|4|–>|80|2|–>|22|-1|

Delete item present at location 10
There are less than 10 elements in list
–>|55|1|–>|67|4|–>|80|2|–>|22|-1|

Search ’1′ in the list
Element not found

*/

Sem3 DSF: Queue Implementation

/*program for Queue implementation*/

class Queue
{
/*array is used to hold queue elements*/
/*two integer variables are used for front and rear pointers*/
int items[]=new int[10];
int front,rear;

Queue()
{/*create queue*/
front=0;
rear=-1;
}/*end createqueue*/

void insert(int e)
{/*if queue is not full insert new element at rear end of queue*/
if(rear==9)
System.out.println(“Queue overflow”);
else
{

items[++rear]=e;
}
}/*end insert*/

int empty()
{/*Return 1 if queue is empty and 0 otherwise*/

return(rear<front? 1:0);
}/*end empty*/

void remove()
{/*if queue is not empty remove one element from front */
if(empty()==1)
System.out.println(“Queue Underflow”);
else
System.out.println(“Removed element : “+items[front++]);
/*end else*/
}/*end rem*/

void display()
{/*Display all elements from front to rear end of queue*/
if(empty()==0)
{
System.out.println(“Queue : “);
int t=front;
while(t<=rear)
System.out.print(” “+items[t++]);
System.out.println();

}
}/*end display*/

}

class QSimple
{
public static void main(String args[])
{
Queue q=new Queue();
int i,j;
System.out.println(“Starting…”);
for(i=0;i<=10;i++)
{
j = new Integer((int)(Math.random() * 100));
System.out.println(“Insert: ” + j);
q.insert(j);
}
q.display();
while(q.empty()==0)
{
q.remove();
}
q.remove();
System.out.println(“Done “);
}/*end main*/
}

/*
starting…
Insert: 27
Insert: 69
Insert: 77
Insert: 26
Insert: 96
Insert: 57
Insert: 88
Insert: 23
Insert: 47
Insert: 94
Insert: 68
Queue overflow
Queue :
27 69 77 26 96 57 88 23 47 94
Removed element : 27
Removed element : 69
Removed element : 77
Removed element : 26
Removed element : 96
Removed element : 57
Removed element : 88
Removed element : 23
Removed element : 47
Removed element : 94
Queue Underflow
Done
Press any key to continue . . .*/

Sem3 DSF: Stack Operations

class Stack
{
int stk[]=new int[10];
int top;
Stack()
{
top=-1;
}
void push (int item)
{
if (top==9)
System.out.println(“Stack overflow”);
else
stk[++top]=item;
}/*end push*/

boolean isempty()
{
if (top<0)
return true;
else
return false;
}/*end isempty*/

int pop()
{
if (isempty())
{
System.out.println(“Stack underflow”);
return 0;
}
else
return (stk[top--]);
}/*end pop*/

void stacktop()
{
if(isempty())
System.out.println(“Stack underflow “);
else
System.out.println(“Stack top is “+(stk[top]));
}/*end stacktop*/

void display()
{
System.out.println(“Stack–>”);
for(int i=0;i<=top;i++)
System.out.println(stk[i]);
}/*end display*/
}

class MyStack
{
public static void main(String args[])
{
Stack s=new Stack();

//push some numbers onto the stack
for(int i=1;i<=5;i++)
s.push(i);

s.stacktop();
s.display();
//pop some numbers from the stack
for(int i=1;i<=3;i++)
System.out.println(“Popped element : “+s.pop());
s.stacktop();
s.display();

}
}

/*
Stack top is 5
Stack–>
1
2
3
4
5
Popped element : 5
Popped element : 4
Popped element : 3
Stack top is 2
Stack–>
1
2
*/

Sem3 DSF: Bubble Sort

/* Program to implement bubble sort */

import java.io.DataInputStream;   // to load DataInputStream class

class BubbleDemo1
{
public static void main(String args[ ])
{
int i,n=0;
int x[]=new int[25];
DataInputStream in = new DataInputStream(System.in);

try
{
System.out.print(“Enter how many numbers to be sorted : “);
n = Integer.parseInt(in.readLine());
System.out.println(“Enter “+n+” numbers in any order….”);
for(i=0;i<n;i++)
{
System.out.print(“\t\tElement x["+(i+1)+"]=”);
x[i] = Integer.parseInt(in.readLine());
}
}
catch(Exception e) {  System.out.println(“I/O Error”);   }

bubble(x,n);  // Call to bubble
System.out.println(“\nSorted Elements are :”);
for(i=0;i<n;i++)
System.out.println(“\t\tElement x["+(i+1)+"]=”+x[i]);

}

//Bubble Sort Function

static void bubble(int x[],int n)
{
int hold,j,pass;
for(pass=0;pass<n-1;pass++)
{
/*outer loop controls the number of passess*/
/*initially no interchanges have been made on this pass*/
for(j=0;j<n-1;j++)
{
/*inner loop governs each individual pass*/
if(x[j]>x[j+1])
{
/*intetchange elements if they are out of order*/
hold=x[j];
x[j]=x[j+1];
x[j+1]=hold;
}/*end if*/
}
}/*end for*/
}/*end bubble function*/

}

Sem3 DSF: Selection Sort

/* Program to implement Selection Sort */
/*  Input:Unsorted Array
Output:Sorted Array   */

import java.io.DataInputStream;   // to load DataInputStream class

class SelectionSort
{
public static void main(String args[ ])
{
int i,n=0;
int increments[]={5,3,1};
int x[]=new int[25];
DataInputStream in = new DataInputStream(System.in);

try
{
System.out.print(“Enter how many numbers to be sorted : “);
n = Integer.parseInt(in.readLine());
System.out.println(“Enter “+n+” numbers in any order….”);
for(i=0;i<n;i++)
{
System.out.print(“\t\tElement x["+(i+1)+"]=”);
x[i] = Integer.parseInt(in.readLine());
}
}
catch(Exception e) {  System.out.println(“I/O Error”);   }

selection(x,n); // Call to Selection Sort
System.out.println(“\nSorted Elements are :”);
for(i=0;i<n;i++)
System.out.println(“\t\tElement x["+(i+1)+"]=”+x[i]);

}

//Selection Sort Function

static void selection(int x[],int n)
{
int i,indx,j,large;
for(i=n-1;i>0;i–)
{
/*place the largest number ofx[0] through
x[i] into large and its index into indx*/
large=x[0];
indx=0;

for(j=1;j<=i;j++)
if(x[j]>large)
{
large=x[j];
indx=j;
}/*end for…if*/
x[indx]=x[i];
x[i]=large;

for(int v=0;v<n;v++)
System.out.print(“\t”+x[v]);
System.out.println();
}/*end for*/
}/*end select sort*/

}

Sem3 DSF: Merge Sort

/* Program to implement Merge Sort */
/*  Input:Unsorted Array
Output:Sorted Array   */

import java.io.DataInputStream;   // to load DataInputStream class

class MergeSort
{
public static void main(String args[ ])
{
int i,n=0;
int increments[]={5,3,1};
int x[]=new int[25];
DataInputStream in = new DataInputStream(System.in);

try
{
System.out.print(“Enter how many numbers to be sorted : “);
n = Integer.parseInt(in.readLine());
System.out.println(“Enter “+n+” numbers in any order….”);
for(i=0;i<n;i++)
{
System.out.print(“\t\tElement x["+(i+1)+"]=”);
x[i] = Integer.parseInt(in.readLine());
}
}
catch(Exception e) {  System.out.println(“I/O Error”);   }

merge(x,n); // Call to Merge Sort
System.out.println(“\nSorted Elements are :”);
for(i=0;i<n;i++)
System.out.println(“\t\tElement x["+(i+1)+"]=”+x[i]);

}

//Merge Sort Function

static void merge(int x[],int n)
{
int sub[] = new int[25];
int i,j,k,l1,l2,u1,u2,size;
size=1;                         //Merge files of size 1
while(size<n)
{
l1=0;                       // Initialize lower bounds of first file
k=0;                        // k is index for auxiliary array

while((l1+size)<n)         // Check to see if there are two files to merge
{
l2=l1+size;           // Compute remaining indices
u1=l2-1;
u2=((l2+size-1)<n)?(l2+size-1):(n-1);

// Proceed through the two subfiles
for(i=l1,j=l2;i<=u1 && j<=u2;k++)
if(x[i]<=x[j])
sub[k]=x[i++];
else
sub[k]=x[j++];

/*At this point, one of the subfiles has been exhausted. Insert any remaining portions of the other file*/
for(;i<=u1;k++)
sub[k]=x[i++];
for(;j<=u2;k++)
sub[k]=x[j++];
// Advance l1 to the start of the next pair of files.
l1=u2+1;
}   // end of while

//Copy any remaining single file
for(i=l1;k<n;i++)
sub[k++]=x[i];

//Copy aux into x and adjust size
for(i=0;i<n;i++)
x[i]=sub[i];
size*=2;
}  // end of while
}   // end of merge sort function

}