MERGE SORT IN JAVA

MERGE SORT IN JAVA

package mergesort;

import java.util.Random;

import java.util.Scanner;

public class Demo {

public static void Display(int A[]){

for(int i=0;i<A.length;i++){

System.out.print(A[i]+" ");

}

}

public static void mergesort(int A[]){

int n=A.length;

if(n<2){

return;

}

int mid=n/2;

int LA[]=new int[mid];

int RA[]=new int[n-mid];

for(int i=0;i<mid;i++){

LA[i]=A[i];

}

for(int i=mid;i<n;i++){

RA[i-mid]=A[i];

}

mergesort(LA);

mergesort(RA);

merge(A,LA,RA);

}

public static void merge(int A[],int LA[], int RA[]){

int n=A.length;

int nl=LA.length;

int nr=RA.length;

int i=0,j=0,k=0;

while(i< nl && j<nr){

if(LA[i]<RA[j]){

A[k]=LA[i];

i++;

k++;

}else{

A[k]=RA[j];

j++;

k++;

}

}

while(i<nl){

A[k]=LA[i];

i++;

k++;

}

while(j<nr){

A[k]=RA[j];

j++;

k++;

}

}

public static void main(String args[]){

Scanner in=new Scanner(System.in);

Random random=new Random();

int s;

System.out.println("Enter the size of the Array");

s=in.nextInt();

int A[]=new int[s];

for(int i=0;i<s;i++){

A[i]=random.nextInt(100);

}

Display(A);

mergesort(A);

System.out.println("\nSorted");

Display(A);

}

}

QUICK SORT IN JAVA

QUICK SORT IN JAVA

package quicksort;

import java.util.Random;

import java.util.Scanner;

public class Demo {

public static void Display(int A[]){

for(int i=0;i<A.length;i++){

System.out.print(A[i]+" ");

}

}

public static void quicksort(int A[],int start, int end){

if(start>=end){

return;

}

int pIndex=partition(A,start,end);

quicksort(A,start,pIndex-1);

quicksort(A,pIndex+1,end);

}

public static int partition(int a[],int s, int e){

int piviot = a[e];

int pindex=s;

for(int i=s;i<e;i++){

if(a[i]<=piviot){

// swapping

int temp= a[pindex];

a[pindex]=a[i];

a[i]=temp;

pindex++;

}

}

a[e]=a[pindex];

a[pindex]=piviot;

return pindex;

}

public static void main(String args[]){

Scanner in=new Scanner(System.in);

Random random=new Random();

int s;

System.out.println("Enter the size of the Array");

s=in.nextInt();

int A[]=new int[s];

for(int i=0;i<s;i++){

A[i]=random.nextInt(100);

}

Display(A);

quicksort(A,0,s-1);

System.out.println("\nSorted");

Display(A);

}

}

Dijkstra's algorithm in java

Dijkstra's algorithm in java

package dijkstra;

import java.util.Scanner;

public class Demo {

int no_nodes;

int matrix[][];

int s; // source

int d[];// distance

int p[]; // parent

boolean visited[]; // to track visited node

Scanner in=new Scanner(System.in);

public void input(){

System.out.println("Enter no. of Nodes");

no_nodes=in.nextInt();

matrix=new int[no_nodes][no_nodes];

d=new int[no_nodes];

p=new int[no_nodes];

visited=new boolean[no_nodes];

System.out.println("Enter connection matrix");

System.out.print("  ");

for(int i=0;i<no_nodes;i++){

char ch=(char)(65+i);

System.out.print(ch+"\t");

}

System.out.println();

for(int i=0;i<no_nodes;i++){

System.out.print((char)(65+i));

for(int j=0;j<no_nodes;j++){

matrix[i][j]=in.nextInt();

}

System.out.println();

}

}

public void initialize(){

for(int i=0;i<no_nodes;i++){

d[i]=1000; // infinity

p[i]=-1 ;// nil for parents

visited[i]=false;

}

d[s]=0;

}

public int findVertex(){

int min=1000;

int vertex=0;

for(int i=0;i<no_nodes;i++){

if(visited[i]==false && d[i]<min){

min=d[i];

vertex=i;

}

visited[vertex]=true;

}

return vertex;

}

public void algorithm(){

System.out.println("Enter source");

s=in.nextInt();

initialize();

int c=no_nodes;

while(c>0){

// find vertex to go

int vertex=findVertex();

c--;

for(int i=0; i<no_nodes;i++){

if(matrix[vertex][i]>0){

// relax

int dis=matrix[vertex][i];

if(dis+d[vertex]<d[i]){

d[i]=dis+d[vertex];

p[i]=vertex;

}

}

}

}

System.out.println("Source= "+(char)(65+s));

System.out.println();

System.out.print(" ");

System.out.print("\tD"+"\tP\n");

for(int i=0;i<no_nodes;i++){

System.out.print((char)(65+i)+"\t");

System.out.print(d[i]+"\t");

System.out.print((char)(65+p[i])+"\n");

}

}

public static void main(String args[]){

Demo obj=new Demo();

obj.input();

obj.algorithm();

}

}

banker's algorithm in java

Banker's algorithm in java

optimal page replacement in java

Optimal page replacement in java

package pagereplacement;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

public class Demo {

String ref="";

int size=0;

int pf=0;

char frame[];

int fc=0;

Scanner input=new Scanner(System.in);

public void input(){

System.out.println("Enter Ref. String");

ref=input.next();

System.out.println("Enter Frame size");

size=input.nextInt();

frame=new char[size];

}

public boolean search(char ch){

for(int i=0;i<fc;i++){

char temp=frame[i];

if(temp==ch){

return true;

}

}

return false;

}

public int future(char ch, int pos){

int result=ref.length()+1;

for(int i=pos+1;i<ref.length();i++){

char temp=ref.charAt(i);

if(temp==ch){

if(i<result){

result=i;

}

}

}

return result;

}

public void optimal(){

System.out.println("Lenght="+ref.length());

for(int i=0;i <ref.length();i++){

char ch=ref.charAt(i);

if(search(ch)){

}else{

// page fault

System.out.print("Page fault At index "+i);

pf++;

if(fc<size){

frame[fc]=ch;

fc++;

}else{

int optimal[]=new int[size];

for(int j=0;j<size;j++){

optimal[j]=future(frame[j],i);

}

// to find the page to be replaced

int index=0;

int max=optimal[0];

for(int j=1;j<size;j++){

if(optimal[j]>max){

max=optimal[j];

index=j;

}

}

// replace page

System.out.print(" and page "+ frame[index]+" is repaced by "+ch);

frame[index]=ch;

}

System.out.println();

}

}

System.out.println("No. of Page fault="+pf);

}

public static void main(String args[]){

Demo obj=new Demo();

obj.input();

obj.optimal();

}

}

//70120304230321201701