import java.io.*;
class HeapSort
{
static int[] a;
static int limit;
static int c=0,m=0; //variables to keep track of comparisons and moves
public static void reHeap(int k)
{
if( 2*k+1 > limit)
return;
if( 2*k+2 > limit)
{
c++;
if(a[k]<a[2*k+1])
{
swap(k,2*k+1);
reHeap(2*k+1);
}
return;
}
c+=2;
if(a[2*k+1]>a[k] || a[2*k+2]>a[k])
{
c++;
if(a[2*k+1]>a[2*k+2])
{
swap(k,2*k+1);
reHeap(2*k+1);
}
else
{
swap(k,2*k+2);
reHeap(2*k+2);
}
return;
}
}
public static void swap(int x, int y)
{
int temp = a[x];
a[x] = a[y];
a[y] = temp;
m+=3;
}
public static void main(String[] args)
{
try
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter name of the source file: ");
FileReader fr =new FileReader(br.readLine());
char[] buffer = new char[2048];
int len = fr.read(buffer);
String data = new String(buffer,0,len);
String[] element = data.split(",");
a = new int[element.length];
System.out.println("\n\nBefore Sorting: ");
for(int i=0; i<a.length; i++)
{
a[i] = Integer.parseInt(element[i]);
System.out.print(a[i]+"\t");
}
//Main logic of heap sort
for(limit=a.length-1; limit>0; limit--)
{
for(int i=limit; i>=0; i--)
reHeap(i);
swap(0,limit);
}
System.out.println("\n\nAfter Sorting: ");
for(int i=0; i<a.length; i++)
{
System.out.print(a[i]+"\t");
}
System.out.println("\n\nComparisons = " + c + "\tMoves = " + m);
}
catch (Exception e)
{
e.printStackTrace();
}
}
}
Sunday, 29 April 2012
Heap Sort in Java
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment
Your comments are very much valuable for us. Thanks for giving your precious time.