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  }