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.