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.

## All 5 Replies

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);
}``````

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

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 ;)

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 ;)

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?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.