MERGE SORT ALGORITHM

/*

TOPIC: MERGE SORT ALGORITHM.
DATE:4/10/2012
*/
import java.io.*;
class Sequence
{
BufferedReader br;
int a[];
int size,temp;
boolean flag;
int l1,l2,l3,k,a1,a2,i,j;
Sequence()
{
br = new BufferedReader ( new InputStreamReader(System.in));
flag=true;
}
void create()throws IOException
{
System.out.println("enter size of array: ");
size=Integer.parseInt(br.readLine());
a=new int[size];
insert();
}
void insert()throws IOException
{
System.out.println("INSERT THE ELEMENTS INTO THE ARRAY");
for(i=0;i<size;i++)
a[i]=Integer.parseInt(br.readLine());
}
void MergeSort()

{
MergeSort(0,a.length-1);
}
void MergeSort(int lo,int n)

{
int low=lo;
int high=n;
if(low>=high)
return;
int middle=(low+high)/2;
MergeSort(low,middle);
MergeSort(middle+1,high);
int end_low=middle;
int start_high=middle+1;
while((low<=end_low)&&(start_high<=high))
{
if(a[low]<a[start_high])
{
low++;
}
else{
int temp=a[start_high];
for(int k=start_high-1;k>=low;k--)
a[k+1]=a[k];
a[low]=temp;
low++;
end_low++;
start_high++;
}
}
}

void display()
{
for(i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
}
class MergeSort
{
public static void main(String args[])throws Exception
{
Sequence s=new Sequence();
s.create();
System.out.println("BEFORE SORTING");
s.display();
s.MergeSort();
System.out.println("AFTER SORTING");
s.display();
//System.out.println("THANK U CODED BY TG");
}
}
/*
OUTPUT:
enter size of array:
8
INSERT THE ELEMENTS INTO THE ARRAY
55
4
98
7
65
26
3
444
BEFORE SORTING
55              4               98              7               65             26               3               444
AFTER SORTING
3               4               7               26              55             65               98              444

*/

INSERTION SORT ALGORITHM IN JAVA.

/*
TOPIC: INSERTION SORT ALGORITHM IN JAVA.
DATE:19/9/2012
*/
import java.io.*;
class Sequence
{
BufferedReader br;
int a[];
int size,temp;
boolean flag;

Sequence()
{
br = new BufferedReader ( new InputStreamReader(System.in));
flag=true;
}
void create()throws IOException
{
System.out.println("enter size of array: ");
size=Integer.parseInt(br.readLine());
a=new int[size];
insert();
}
void insert()throws IOException
{
System.out.println("INSERT THE ELEMENTS INTO THE ARRAY");
for(int i=0;i<size;i++)
a[i]=Integer.parseInt(br.readLine());
}
void insertionsort()
{ int j=0;
for(int i=1;i<a.length;i++)
{
temp=a[i];
j=i;
while(j>0&&a[j-1]>=temp)
{
a[j]=a[j-1];
j--;
}
a[j]=temp;
}
System.out.println("AFTER SORTING");
display();
}

void display()
{
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
}
class insertionsort
{
public static void main(String args[])throws Exception
{
Sequence s=new Sequence();
s.create();
System.out.println("BEFORE SORTING");
s.display();
s.insertionsort();
System.out.println("THANK U CODED BY TG");
}
}
/*
OUTPUT:
enter size of array:
8
INSERT THE ELEMENTS INTO THE ARRAY
200
14
96
48
555
422
316
122
BEFORE SORTING
200             14              96              48              555             422             316             122
AFTER SORTING
14              48              96              122             200             316             422             555
THANK U CODED BY TG
*/

HEAP SORT ALGORITHM IN JAVA.

/*
TOPIC: HEAP SORT ALGORITHM.
DATE:3/10/2012
*/

import java.io.*;
class Sequence
{
int size;
int i;
int a[]=new int[25];
BufferedReader br;
Sequence()
{
br = new BufferedReader ( new InputStreamReader(System.in));
}
void create()throws IOException
{
System.out.println("enter size of array: ");
size=Integer.parseInt(br.readLine());
a=new int[size];
insert();
}
void insert()throws IOException
{
System.out.println("INSERT THE ELEMENTS INTO THE ARRAY");
for(int i=0;i<size;i++)
a[i]=Integer.parseInt(br.readLine());
}

void display()
{
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
void HeapSort()
{
int n=size;
int i,elt,s,f,ivalue,pass=1;
    for(i=1;i<n;i++)
    {
elt=a[i];
s=i;
f=(s-1)/2;
while((s>0)&&(a[f]<elt))
{
   a[s]=a[f];
   s=f;
   f=(s-1)/2;
}
a[s]=elt;
    }
    for(i=n-1;i>0;i--)
    {
ivalue=a[i];
a[i]=a[0];
f=0;
if(i==1)
s=-1;
else
s=1;
if((i>2)&&(a[2]>a[1]))
s=2;
while((s>=0)&&(ivalue<a[s]))
{
   a[f]=a[s];
   f=s;
   s=2*f+1;
   if((s+1<=i-1)&&(a[s]<a[s+1]))
       s=s+1;
   if(s>(i-1))
s=-1;
}
       a[f]=ivalue;
System.out.println();
    }

}
}  
class HeapSort
{
public static void main(String args[])throws IOException
{
      Sequence s=new Sequence();
s.create();
System.out.println("BEFORE SORTING:");
s.display();
    s.HeapSort();
    System.out.println("AFTER SORTING:");
 
s.display();
}

}
/*
OUTPUT:
enter size of array:
8
INSERT THE ELEMENTS INTO THE ARRAY
25
4
65
9
555
1
23
12
BEFORE SORTING:
25              4               65              9               555            23               12
AFTER SORTING:
1               4               9               12              23             25               65              555

*/

BINARY SEARCH ALGORITHM IN JAVA.

/*
TOPIC: BINARY SEARCH ALGORITHM.
DATE:9/10/2012
*/
import java.util.*;
import java.io.*;
class binsearch
{
int a[];
int size,middle,left,right,key;
PrintStream p=System.out;
Scanner sc=new Scanner(System.in);
binsearch()
{
sc=new Scanner(System.in);

}
void getData()
{


p.println("enter array size");
size=sc.nextInt();
a=new int[size];
p.println("enter array the array");
for(int i=0;i<a.length;i++)

{
p.print("a["+(i)+"] =");
a[i]=sc.nextInt();
}
p.println("the array is");
for(int i=0;i<a.length;i++)
{
p.print(a[i]+" ");
}
p.println();

this.SelectionSort();
this.getKey();

}
void getKey()
{

p.print("enter key: ");
key=sc.nextInt();
this.binsearch();
}
void swap(int i,int j)
{
a[i]=a[i]*a[j];
a[j]=a[i]/a[j];
a[i]=a[i]/a[j];
}
void display()
{
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
void binsearch()
{
boolean flag=true;
left=0;
right=size-1;
while(left<=right)
{
middle=(left+right)/2;
if(key==a[middle])
{
flag=false;
p.println("the element is found at the "+middle+" position");
break;
}
if(key<a[middle])
{
right=middle - 1;
}
if(key>a[middle])
{
left=middle + 1;
}
}
if(flag)
p.println("element not found");
}
void SelectionSort()
{
for(int i=0;i<a.length-1;i++)
{

for(int j=i+1;j<a.length;j++)
{
if(a[j]<a[i])
swap(j,i);

}
}
System.out.println("AFTER SORTING--we used seletion sort");
display();
}
public static void main(String args[])throws Exception
{
binsearch b=new binsearch();
b.getData();
}
}
/*
OUTPUT:
enter array size
8
enter array the array
a[0] =25
a[1] =1
a[2] =245
a[3] =655
a[4] =22
a[5] =885
a[6] =65
a[7] =36
the array is
25      1       245     655     22      885     65      36
AFTER SORTING--we used seletion sort
1               22              25              36              65             245              655             885
enter key: 655
the element is found at the 6
*/

BUBBLE SORT ALGORITHM.

/*
TOPIC: BUBBLE SORT ALGORITHM.
SEIT
DATE:19/9/2012
*/
import java.io.*;
class Sequence
{
BufferedReader br;
int a[];
int size,temp;
boolean flag;

Sequence()
{
br = new BufferedReader ( new InputStreamReader(System.in));
flag=true;
}
void create()throws IOException
{
System.out.println("enter size of array: ");
size=Integer.parseInt(br.readLine());
a=new int[size];
insert();
}
void insert()throws IOException
{
System.out.println("INSERT THE ELEMENTS INTO THE ARRAY");
for(int i=0;i<size;i++)
a[i]=Integer.parseInt(br.readLine());
}
void BubbleSort()
{
for(int i=0;i<a.length && flag==true;i++)
{
flag=false;
for(int j=0;j<a.length-1;j++)
{
if(a[j]>a[j+1])
swap(j,j+1);

}
}
System.out.println("AFTER SORTING");
display();
}
void swap(int i,int j)
{ flag=true;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
void display()
{
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
}
class Bubblesort
{
public static void main(String args[])throws Exception
{
Sequence s=new Sequence();
s.create();
System.out.println("BEFORE SORTING");
s.display();
s.BubbleSort();
System.out.println("THANK U CODED BY TG");
}
}
/*
OUTPUT:
enter size of array:
8
INSERT THE ELEMENTS INTO THE ARRAY
22
53
43
35
11
93
85
32
BEFORE SORTING
22              53              43              35              11              93              85              32
AFTER SORTING
11              22              32              35              43              53              85              93
THANK U CODED BY TG
*/

SELECTION SORT ALGORITHM.

/*
TOPIC: SELECTION SORT ALGORITHM.
DATE:19/9/2012
*/
import java.io.*;
class Sequence
{
BufferedReader br;
int a[];
int size,temp;
boolean flag;

Sequence()
{
br = new BufferedReader ( new InputStreamReader(System.in));
flag=true;
}
void create()throws IOException
{
System.out.println("enter size of array: ");
size=Integer.parseInt(br.readLine());
a=new int[size];
insert();
}
void insert()throws IOException
{
System.out.println("INSERT THE ELEMENTS INTO THE ARRAY");
for(int i=0;i<size;i++)
a[i]=Integer.parseInt(br.readLine());
}
void SelectionSort()
{
for(int i=0;i<a.length-1;i++)
{

for(int j=i+1;j<a.length;j++)
{
if(a[j]<a[i])
swap(j,i);

}
}
System.out.println("AFTER SORTING");
display();
}
void swap(int i,int j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
void display()
{
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
}
class SelectionSort
{
public static void main(String args[])throws Exception
{
Sequence s=new Sequence();
s.create();
System.out.println("BEFORE SORTING");
s.display();
s.SelectionSort();

System.out.println("THANK U CODED BY TG");
}
}
/*
OUTPUT:
enter size of array:
9
INSERT THE ELEMENTS INTO THE ARRAY
402
54
669
221
74
921
36
55
1
BEFORE SORTING
402             54              669             221             74              921             36              55              1
AFTER SORTING
1               36              54              55              74              221             402             669             921
THANK U CODED BY TG
*/

IMPLEMENTATION OF QUICK SORT ALGORITHM IN JAVA.

/*
TOPIC: QUICK SORT ALGORITHM.
SEIT
DATE:27/9/2012
*/
import java.io.*;
class Sequence
{
BufferedReader br;
int a[];
int size,temp;
boolean flag;
long pivot;
int partition;
Sequence()
{
br = new BufferedReader ( new InputStreamReader(System.in));
flag=true;
}
void create()throws IOException
{
System.out.println("enter size of array: ");
size=Integer.parseInt(br.readLine());
a=new int[size];
insert();
}
void insert()throws IOException
{
System.out.println("INSERT THE ELEMENTS INTO THE ARRAY");
for(int i=0;i<size;i++)
a[i]=Integer.parseInt(br.readLine());
}
void QuickSort()
{ QuickSort(0,size-1);

}

void QuickSort(int l,int r)
{
if(r<l)
return;

partition=partition(l,r);
QuickSort(l,partition-1);
QuickSort(partition+1,r);




}
int partition(int l,int r)
{ int x=a[l];
int up=r;
int down=l;
while(down<up)
{ while(a[down]<=x && down<r)
{
down++;
}
while(a[up]>x)
{
up--;
}
if(down<up)
{
swap(down,up);
}

}
a[l]=a[up];
a[up]=x;
return up;

}

void swap(int up,int down)
{
//used addition swapping algorithm;
a[up]=a[down]+a[up];
a[down]=a[up]-a[down];
a[up]=a[up]-a[down];
}

void display()
{
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
}
class QuickSort
{
public static void main(String args[])throws Exception
{
Sequence s=new Sequence();
s.create();
System.out.println("BEFORE SORTING");
s.display();
s.QuickSort();
System.out.println("AFTER SORTING");
s.display();
System.out.println("THANK U CODED BY TG");
}
}
/*
OUTPUT:
enter size of array:
8
INSERT THE ELEMENTS INTO THE ARRAY
15
444
52
85
96
4
285
26
BEFORE SORTING
15              444             52              85              96             285              26
AFTER SORTING
4               15              26              52              85             96               285             444
THANK U CODED BY TG
*/

RADIX SORT IN JAVA.

/*
TOPIC: RADIX SORT.
DATE:9/8/2012

*/
import java.util.*;
class RadixSort
{
Scanner sc;
 int x[],n,m;
public RadixSort()
{
sc= new Scanner(System.in);
}
void getData()
{

System.out.println("Enter the number of elements");
n=sc.nextInt();
x= new int[n];
System.out.println("Enter the array");
for(int i=0; i<n; i++)
  x[i]=sc.nextInt();

}
public int findMaxDigit()
{
int max=x[0];
for(int i=1; i<n; i++)
  if(x[i]>max)
      max=x[i];
int d=0;
while(max>0)
{
d++;
max=max/10;
}
return d;
}
public void radixSort()
{
int i,j,d;
d=findMaxDigit();
for(int k=1; k<d; k++)
{
int no[][]= new int[10][20], count[]= new int[10];
System.out.println("K = "+k);
for(i=0; i<n; i++)
{
int dig;
dig=x[i]/(int)(Math.pow(10,k-1))%10;
no[dig][count[dig]++]=x[i];
}
j=0;
for(i=0; i<10; i++)
{
int m=0;
while(m<count[i])
{
x[j++]=no[i][m++];
}
}
display();
}
}

public void display()
{
for( int i=0;i<n; i++)
System.out.print(x[i]+" ");
System.out.println();
}
public static void main(String args[])
{
RadixSort obj =new RadixSort();
obj.getData();
obj.radixSort ();
System.out.println("Sorted Array");
obj.display();
}
}
/*Output
Enter the number of elements
5
Enter the array
1
20
2
30
3
K = 1
20 30 1 2 3
Sorted Array
1 2 3 20 30
*/

SELECTION SORT ALGORITHM IN JAVA.

/*
TOPIC: SELECTION SORT ALGORITHM.
DATE:19/9/2012
*/
import java.io.*;
class Sequence
{
BufferedReader br;
int a[];
int size,temp;
boolean flag;

Sequence()
{
br = new BufferedReader ( new InputStreamReader(System.in));
flag=true;
}
void create()throws IOException
{
System.out.println("enter size of array: ");
size=Integer.parseInt(br.readLine());
a=new int[size];
insert();
}
void insert()throws IOException
{
System.out.println("INSERT THE ELEMENTS INTO THE ARRAY");
for(int i=0;i<size;i++)
a[i]=Integer.parseInt(br.readLine());
}
void SelectionSort()
{
for(int i=0;i<a.length-1;i++)
{

for(int j=i+1;j<a.length;j++)
{
if(a[j]<a[i])
swap(j,i);

}
}
System.out.println("AFTER SORTING");
display();
}
void swap(int i,int j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
void display()
{
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
}
class SelectionSort
{
public static void main(String args[])throws Exception
{
Sequence s=new Sequence();
s.create();
System.out.println("BEFORE SORTING");
s.display();
s.SelectionSort();

System.out.println("THANK U CODED BY TG");
}
}
/*
OUTPUT:
enter size of array:
9
INSERT THE ELEMENTS INTO THE ARRAY
402
54
669
221
74
921
36
55
1
BEFORE SORTING
402             54              669             221             74              921             36              55              1
AFTER SORTING
1               36              54              55              74              221             402             669             921
THANK U CODED BY TG
*/