import java.io.*;
class HeapSortLC
{
static int[] a;
static int limit;
static int constant=1;
static int c=0,m=0; //variables to keep track of comparisons and moves
public static void reHeapLightBubble(int k)
{
if( 2*k+constant > a.length-1)
return;
if( 2*k+(constant+1) > a.length-1)
{
c++;
if(a[k]>a[2*k+constant])
{
swap(k,2*k+constant);
reHeapLightBubble(2*k+constant);
}
return;
}
c+=2;
if(a[2*k+constant]<a[k] || a[2*k+(constant+1)]<a[k])
{
c++;
if(a[2*k+constant]<a[2*k+(constant+1)])
{
swap(k,2*k+constant);
reHeapLightBubble(2*k+constant);
}
else
{
swap(k,2*k+(constant+1));
reHeapLightBubble(2*k+(constant+1));
}
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 with left curtailment
for(int i=a.length-1; i>=0; i--)
{
reHeapLightBubble(i);
}
constant--;
for(limit=1; limit<a.length-1; limit++)
{
reHeapLightBubble(limit);
constant--;
}
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 with left curtailment in Java (Best)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment
Your comments are very much valuable for us. Thanks for giving your precious time.