1 /******************************************************** 2 * heapsort.cpp 3 * C++ HeapSort. 4 * Compiled on GNU g++ compiler and Visual C++ compiler. 5 * Author: John Bryan, Jr. 6 * Date: August 27, 2006 7 * Reads variable number of integers from file integers.txt. 8 * Writes sorted integers to file sorted.integers.txt and 9 * to the screen. 10 *********************************************************/ 11 # include <iostream> 12 # include <stdio.h> 13 using namespace std; 14 15 16 class HeapSorter 17 { 18 int N,Number,i,j,k,element,*A; 19 FILE *fp; 20 void GetIntegers(); 21 void PrintA(); 22 void FilePrintA(); 23 void InitializeA(); 24 void ConstructHeap(); 25 void HeapSort(); 26 void BubbleDown(); 27 void Swap(); 28 public: 29 void Algorithm(); 30 }HS; 31 32 33 void HeapSorter::BubbleDown() 34 { 35 j=i; 36 do 37 { 38 k=j; 39 if(((2*k+1)<N)&&(A[2*k+1]>A[j])) 40 j=2*k+1; 41 if(((2*k+2)<N)&&(A[2*k+2]>A[j])) 42 j=2*k+2; 43 Swap(); 44 }while(k!=j); 45 } 46 47 48 void HeapSorter::ConstructHeap() 49 { 50 for (i=N-1; i>=0; i--) 51 BubbleDown(); 52 return; 53 } 54 55 56 void HeapSorter::HeapSort() 57 { 58 for (int r=N-1; r>0; r--) 59 { 60 k=r; 61 j=0; 62 Swap(); 63 i=0; 64 N=r; 65 BubbleDown(); 66 } 67 cout << "\nThe sorted integers are " << "\n"; 68 PrintA(); 69 FilePrintA(); 70 delete []A; 71 fclose(fp); 72 return; 73 } 74 75 76 void HeapSorter::Swap() 77 { 78 int temp; 79 temp = *(A+k); 80 *(A+k) = *(A+j); 81 *(A+j) = temp; 82 return; 83 } 84 85 86 void HeapSorter::PrintA() 87 { 88 int s; 89 cout << " "; 90 for (int s=0;s<Number;s++) 91 cout << *(A+s) << " "; 92 cout << "\n"; 93 } 94 95 96 void HeapSorter::FilePrintA() 97 { 98 int k; 99 fp = fopen("sorted.integers.txt","w"); 100 if (fp == NULL) 101 { 102 printf("File open failure.\n"); 103 exit(1); 104 } 105 for(k=0;k<Number;k++) 106 { 107 fprintf(fp,"%d ",*(A+k)); 108 if((k+1)%10==0)fprintf(fp,"\n"); 109 } 110 fprintf(fp, "\n"); 111 fclose(fp); 112 } 113 114 115 void HeapSorter::InitializeA() 116 { 117 int m; 118 A= new int[N]; 119 for (int m=0;m<N;m++) 120 *(A+m)=0; 121 } 122 123 124 void HeapSorter::GetIntegers() 125 { 126 int r=0,number=0; 127 fp=fopen("integers.txt" ,"r"); 128 N=0; 129 while (fscanf(fp,"%d", &number)!=EOF) 130 N++; 131 Number=N; 132 fclose(fp); 133 InitializeA(); 134 fp=fopen("integers.txt" ,"r"); 135 while(fscanf(fp,"%d", &number)!=EOF) 136 { 137 *(A+r)=number; 138 r++; 139 } 140 fclose(fp); 141 cout << "\nThe number of integers to be sorted is " << N << ".\n"; 142 cout << "\nThe integers to be sorted are\n"; 143 PrintA(); 144 return; 145 } 146 147 148 void HeapSorter::Algorithm() 149 { 150 GetIntegers(); 151 ConstructHeap(); 152 HeapSort(); 153 } 154 155 156 int main() 157 { 158 HS.Algorithm(); 159 return 0; 160 }