Trouble with Heap Sort, array heapified, just cant get sorted.

[bigmaq]

Hi, so I have put up two posts in the last day on this program. I am quite new at this concept of Heaps and Heap Sort and I have done a lot of work figuring this out, but i am very close to getting it. I do have my array of integers being "Heapified", now I need to sort it so that the elements of the array from smallest to greatest. Here is my code so far, the part I am having trouble with is my function void Heapsort::sort(). I can't seem to get my for loop to work. I will show the output I have been getting after the code.

#include<iostream>
using namespace std;
 
class Heapsort
{
  private:
     int *array;
     int mysize;
  public:
     Heapsort(int);
     ~Heapsort();
     int percolate_down(int);
     void heapify();
     void sort();
     void fill_array();
     void print();
};
    
Heapsort::Heapsort(int a)
{  
   mysize = a;
   int *array = new int[mysize];
   array[NULL];
}
          
Heapsort::~Heapsort()
{
   delete [] array;
}
          
void Heapsort::fill_array()
{
    int i;
          
    for (i = 1; i < mysize; i++){
       cout << "\nEnter a number: ";
       cin >> array[i];
    }
  
    print();    //This prints the array before Heapify.
}
  
int Heapsort::percolate_down(int r)
{
    int t=0;
    int c = 2*r;
   
    while (r < mysize)  
    {
        if ((c < mysize) && (array[c] < array[c+1]))
        {
          c++;
        }
        if (array[r] < array[c])
        {
          t = array[c];
          array[c] = array[r];
          array[r] = t;
          r=c;
          c=2*c;
          print();  //prints the progress of the heapifying
        }else{
          break;
         }
    }
  
    return (r);
}
  
void Heapsort::heapify()
{
   int r = mysize/2;
    
   for(r; r > 0; r--){
      percolate_down(r);
   } 
}
  
void Heapsort::sort()
{
   int r;
   int t=0;
          
   heapify(); 
          
   for (r=mysize; r >= 2; r--){
      t = array[1];
      array[1] = array[r-1];
      array [r-1] = t;
   }
}
  
void Heapsort::print()
{
  int j;
  cout << endl << endl;
  for (j=1; j < mysize; j++)
        cout << array[j] << "  ";
}   
    
int main()
{
  Heapsort heap(16);
  
  cout << endl << endl;

  heap.fill_array();      
  heap.sort();
   
  cout << "\n\nthis is the sorted array: \n";
      
  heap.print();
      
  cout << endl << endl;
    
  return (0);
}

This is the output if you enter 1 - 15 as the values of the array:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 2 3 4 5 6 15 8 9 10 11 12 13 14 7

1 2 3 4 5 13 15 8 9 10 11 12 6 14 7

1 2 3 4 11 13 15 8 9 10 5 12 6 14 7

1 2 3 9 11 13 15 8 4 10 5 12 6 14 7

1 2 15 9 11 13 3 8 4 10 5 12 6 14 7

1 2 15 9 11 13 14 8 4 10 5 12 6 3 7

1 11 15 9 2 13 14 8 4 10 5 12 6 3 7

1 11 15 9 10 13 14 8 4 2 5 12 6 3 7

15 11 1 9 10 13 14 8 4 2 5 12 6 3 7

15 11 14 9 10 13 1 8 4 2 5 12 6 3 7

15 11 14 9 10 13 7 8 4 2 5 12 6 3 1

this is the sorted array:

11 14 9 10 13 7 8 4 2 5 12 6 3 1 15

Segmentation fault

P.S> I still havnt figured out why I am getting a Segmentation Fault. The program so far does what its supposed to up to the sorting. ive been getting hte segmentation fault the whole time... :/

Any help is muchly appreciated.

[programmersbook]

Hi,

first of all you should use m_ for member variables and second C++ is NOT C, you should use vector or list you save the data and sort. Just an idea

But here the code twith out segv:

#include<iostream>
using namespace std;
 
class Heapsort
{
  private:
     int *array;
     int mysize;
  public:
     explicit Heapsort(int);
     ~Heapsort();
     
     void allocate_array(int a);
     void destroy_array();
     
     int percolate_down(int);
     void heapify();
     void sort();
     void fill_array();
     void print();
};
    
Heapsort::Heapsort(int a)
{  
    allocate_array(a);
}
          
Heapsort::~Heapsort()
{
   destroy_array();
}

void Heapsort::allocate_array(int a)
{
   mysize = a;
   //int *array was WRONG! it coverted the array member variable!
   array = new int[mysize];
   cout << array << endl;
   //array[NULL]; doesn't do anything
}
void Heapsort::destroy_array()
{
    delete [] array;
}
          
void Heapsort::fill_array()
{
    int i;
    int tmp = 0;
    cout << array << endl;
    // i = 1 is not really want you want
    for (i = 0; i < mysize; i++){
       cout << "\nEnter a number: ";
       cin >> tmp;
       array[i] = 99;
    }
  
    print();    //This prints the array before Heapify.
}
  
int Heapsort::percolate_down(int r)
{
    int t=0;
    int c = 2*r;
   
    while (r < mysize)  
    {
        if ((c < mysize) && (array[c] < array[c+1]))
        {
          c++;
        }
        if (array[r] < array[c])
        {
          t = array[c];
          array[c] = array[r];
          array[r] = t;
          r=c;
          c=2*c;
          print();  //prints the progress of the heapifying
        }else{
          break;
         }
    }
  
    return (r);
}
  
void Heapsort::heapify()
{
   int r = mysize/2;
    
   for(; r > 0; r--){
      percolate_down(r);
   } 
}
  
void Heapsort::sort()
{
   int r;
   int t=0;
          
   heapify(); 
          
   for (r=mysize; r >= 2; r--){
      t = array[1];
      array[1] = array[r-1];
      array [r-1] = t;
   }
}
  
void Heapsort::print()
{
  int j;
  cout << endl << endl;
  for (j=1; j < mysize; j++)
        cout << array[j] << "  ";
}   
    
int main()
{
  Heapsort heap(16);
  
  cout << endl << endl;

  heap.fill_array();      
  heap.sort();
   
  cout << "\n\nthis is the sorted array: \n";
      
  heap.print();
      
  cout << endl << endl;
    
  return (0);
}

[bigmaq]

Thanks for the help with the seg fault ProgrammersBook, but could you show me what you mean by using m_ for member variables? im pretty new to c++ and everything i know how to do i have taught myself cuz my professor doesnt do a very good job of it lol

[programmersbook]

instead of:

int *array;
int mysize;

should be:

int *m_pArray;
int m_nSize;

some people use:
int *_array;
int _size;

or
int *array_;
int size_;

kind of a sign that the variable belogs to the class ;)

[programmersbook]

btw, to find sigv is very easy

compile with -g3 -O0 with gcc

run it

and load the core file with gdb:

gdb ./mybin core

after print where to see the stack trace

have fun ;)

[bigmaq]

ahhhh ok i see. now for the sorting you said use a vector or a list, do you mean getting rid of the array part? or copying?