1 /* 2 * Java HeapSort 3 * Author: John Bryan, Jr. 4 * Date: 09/02/2006 5 * Reads integers from file, integers.txt, performs heapsort, 6 * writes sorted integers to screen and to file, sorted.integers.txt. 7 */ 8 9 10 import java.io.*; 11 import java.util.*; 12 import java.lang.*; 13 14 15 public class hs 16 { 17 private static int k,i,j,N; 18 19 public static int [] ConstructHeap(int []A) throws IOException 20 { 21 for (i=N-1; i>=0; i--) 22 A=Bubbledown(A); 23 return A; 24 } 25 26 27 public static void FilePrintArray(int []A) throws IOException 28 { 29 BufferedWriter output = new BufferedWriter( 30 new FileWriter("sorted.integers.txt")); 31 for (int i=0; i<A.length;i++) 32 { 33 output.write(" " + A[i]); 34 } 35 output.close(); 36 } 37 38 39 public static void HeapSort(int []A) throws IOException 40 { 41 for (int r=N-1; r>0; r--) 42 { 43 k=r; 44 j=0; 45 A=Swap(A); 46 i=0; 47 N=r; 48 A=Bubbledown(A); 49 } 50 System.out.println("The sorted integers are "); 51 PrintArray(A); 52 FilePrintArray(A); 53 return; 54 } 55 56 57 public static int[] Bubbledown(int []A) throws IOException 58 { 59 j=i; 60 do 61 { 62 k=j; 63 if(((2*k+1)<N)&&(A[2*k+1]>A[j])) 64 j=2*k+1; 65 if(((2*k+2)<N)&&(A[2*k+2]>A[j])) 66 j=2*k+2; 67 A=Swap(A); 68 }while(k!=j); 69 return A; 70 } 71 72 73 public static int[] Swap(int []A) throws IOException 74 { 75 int temp; 76 temp=A[k]; 77 A[k]=A[j]; 78 A[j]=temp; 79 return A; 80 } 81 82 83 public static void PrintArray(int []A) throws IOException 84 { 85 for (int i=0; i<A.length;i++) 86 { 87 System.out.print(" " + A[i]); 88 } 89 System.out.println(); 90 } 91 92 93 public static int FindN() throws IOException 94 { 95 String line; 96 N=0; 97 BufferedReader in=new BufferedReader( 98 new FileReader("integers.txt")); 99 while((line = in.readLine()) != null) 100 { 101 int value; 102 String[] words = line.split("\\s+"); 103 for (int m=0;m<words.length;m++) 104 { 105 N++; 106 } 107 } 108 in.close(); 109 return N; 110 } 111 112 113 public static int[] GetIntegers(int[] A) throws IOException 114 { 115 String line; 116 BufferedReader in2 = new BufferedReader( 117 new FileReader("integers.txt")); 118 int q=0; 119 while((line = in2.readLine()) != null) 120 { 121 int value; 122 String[] words = line.split("\\s+"); 123 for (int m=0;m<words.length;m++) 124 { 125 A[q] = Integer.parseInt(words[m].trim()); 126 q++; 127 } 128 } 129 in2.close(); 130 return A; 131 } 132 133 134 public static void main( String[] args ) throws IOException 135 { 136 N=FindN(); 137 int[] A = new int[N]; 138 A=GetIntegers(A); 139 A= ConstructHeap(A); 140 HeapSort(A); 141 System.exit(0); 142 } 143 }