Dynamic Array,HeapSort need help please..

Rayvan (3)
Could someone please help me with a heap sort that would work with an dynamic array,i have the dynamic array already done and i tryed implementing a heap sort function that would sort my array and i had problems doing it could someone help me,thanks in advance:D...I will post my array.cpp,array.h and my test.cpp to make it easier...

This is my array.cpp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
[code]#include "array.h"
#include <iostream>
using namespace std;

#define DEAFULT_MAX_SIZE 5


Array::Array() {
	this->_size = 0;
	this->_elements = new Element[DEAFULT_MAX_SIZE];
	this->_capacity = DEAFULT_MAX_SIZE;
}


Array::~Array() {
	delete this->_elements;
}

int Array::size() {
	return this->_size;
}


Element Array::get_elem(int poz) {
	return this->_elements[poz];
}

void Array::aloca() {
	int i;
	int new_capacity = 2 * this->_capacity;
	Element* new_elements = new Element[new_capacity];
	for (i = 0; i < this->_size; i++) {
		new_elements[i] = this->_elements[i];
	}
	delete this->_elements;
	this->_elements = new_elements;
	this->_capacity = new_capacity;
}


void Array::add(Element el) {
	if (this->_size == this->_capacity - 1) {
		this->aloca();
	}
	this->_elements[_size] = el;
	this->_size++;
}


void Array::addPoz(Element el, int poz) {
	if (this->_size == this->_capacity - 1) {
		this->aloca();
	}
	int i;
	this->_size++;
	for (i = this->_size; i > poz; i--)
		this->_elements[i] = this->_elements[i - 1];
	this->_elements[poz] = el;
}


void Array::removePosition(int poz) {
	this->shiftLeft(poz);
	this->_size--;
}

void Array::shiftLeft(int poz) {
	int i;
	for (i = poz; i < this->_size; i++)
		this->_elements[i] = this->_elements[i + 1];
}


void Array::shiftRight(int poz) {
	int i;
	if (this->_size == this->_capacity - 1)
		this->aloca();
	for (i = poz; i < this->_size; i++)
		this->_elements[i + 1] = this->_elements[i];
	this->_size++;
}


void Array::removeInterval(int a, int b) {
	int j = b - a + 1;
	while (j) {
		this->shiftLeft(a);
		this->_size--;
		j--;
	}
}

void Array::replace(Element* v1, int size1, Element* v2, int size2) {
	int i = 0;
	int j;
	int ok;
	int p;
	while (i < this->_size - size1) {
		ok = 1;
		j = 0;
		while (j < size1 && ok) {
			if (this->_elements[i] == v1[j]) {
				i++;
				j++;
			} else
				ok = 0;
		}
		if (ok) {
			p = i - j;
			this->removeInterval(p, i-1);
			if (size2 > size1) {
				if (this->_size == this->_capacity - 1)
					this->aloca();
			}
			for (j = 0; j < size2; j++) {
				this->addPoz(v2[j], p);
				p++;
			}
		}
		i++;
	}
}



This is my array.h:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
#ifndef ARRAY_H_
#define ARRAY_H_

typedef void* Element;

struct Array{

	int _size;
	Element* _elements;
	int _capacity;
	
        Array();

	
	~Array();

	
	int size();

	
	Element get_elem(int poz);

	
	void aloca();

	
	void add(Element el);

	
	void addPoz(Element el, int poz);


	void removePosition(int poz);

	
	void removeInterval(int a, int b);

	
	void shiftLeft(int poz);
	void shiftRight(int poz);


	void replace (Element* v1, int size1, Element* v2, int size2);
	
};

#endif /* ARRAY_H_ */


And this is my test.c:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
#include<iostream>
#include<assert.h>
#include "array.h"
using namespace std;

void test_array() {
	Array array;
	int a = 2;
	int b = 4;	
	int c = 6;

	assert(array.size()== 0);

	array.add(&a);
	array.add(&b);
	array.add(&c);
	assert(array.size()==3);

	int d = 10;
	array.addPoz(&d, 1);
	assert(array.size()==4);

	int el = *(int *) array.get_elem(1);
	assert(el == d);

	el = *(int *) array.get_elem(3);
	assert(el == c);

	array.removePosition(2);
	el = *(int *) array.get_elem(2);
	assert(el == c);
	assert(array.size() == 3);

	array.addPoz(&b, 2);
	el = *(int *) array.get_elem(2);
	assert(el == b);

	int e = 1;
	int f = 3;
	array.add(&e);
	array.add(&f);
	assert (array.size() == 6);
	assert (array._capacity == 10);

	Element* v1 = new Element[5];
	v1[0]=&b;
	v1[1]=&c;

	int x=9;
	int y=8;
	Element* v2 = new Element[5];
	v2[0]=&x;
	v2[1]=&y;
	v2[2]=&a;

	el = *(int *) array.get_elem(4);
	array.replace(v1,2,v2,3);
	assert (array.size() == 7 );
	el = *(int *)array.get_elem(5);
	assert( el == 1 );
	
	array.removeInterval(2,4);
	assert (array.size() == 4);
	el = *(int *) array.get_elem(2);
	assert (el == e);
}

int main() {
	test_array();
	return 0;
}
[/code]
Last edited on
kbw (9488)
That's a lot of code to read unformatted. Can you please edit your post and use the code format tag to format your code.

All those this-> are unnecessary.
Rayvan (3)
of course..sorry for that and thank you for your interest in helping me:D
kbw (9488)
This looks very Java-esq, but you have some basic C++ errors. The need to cast those points is the clue.

You should do the following to correct it.
1. Change Element from void* to int. This will cause the container to hold values of a specific type, int. If this were to be made generic, you'd use templates to make it generic.

2. As you allocate an array in the constructor, you must use the array delete. That is:
 
 
delete [] _elements;

3. You'll need to revisit replace() as I'm not clear on what it does.

4. When you use the modified class, pass it values as in:
1
2
3
4
5
 
	Array array;
	array.add(a);
	array.add(b);
	array.add(c);
	assert(array.size()==3);
Rayvan (3)
ok....i will consider what you`ve said ...and my problem remains how do i implement HeapSort in this array?can you please write a HeapSort that will work with this dynamic array or if you have a better dynamic array with a HeapSort function that will work,this is a project for an exam that i have for monday.....If you help me i will be very thankful.
kbw (9488)
Surely it's just a matter of implementing the algorithm, there's a description here.
http://en.wikipedia.org/wiki/Heapsort#Pseudocode

If you make a start, the forum can assist. We're a little shy about doing the actual work.
Topic archived. No new replies allowed.