1 /********************************************************
  2 * heapsort.cpp
  3 * C++ HeapSort.
  4 * Compiled on GNU g++ compiler and Visual C++ compiler. 
  5 * Author: John Bryan
  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 }