C++

Forum

 
double free in quicksort

dfith (6)
in main() (m is 5 and x[] is an array of random ints)
1
2
3
4
5
6
7
8
9
10
 
        Quick Q;
	Q.Build(x, m);
	int* x4 = Q.Sort();
	
	cout << endl << endl << "Quick Comparisons: " << Q.comparisons;
	cout << endl << "Sorted array:" << endl;
	for(int i = 0; i < m; i++){
		if(i == m/2 + 1){cout << endl;}
		cout << x4[i] << "  ";
	}


My error is double free, and I get it while I'm printing out x4, so it's after the array has already been built and sorted (build just does class assignments s.t. A = x and n = m).

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
 
int* Quick::Sort(){

	RecursiveSort(0, n - 1);
	return A;
	
}

void Quick::RecursiveSort(int lo, int hi){

	comparisons++;
	if(lo < hi){
		int pIndex = Partition(lo, hi);
		RecursiveSort(lo, pIndex - 1);
		RecursiveSort(pIndex + 1, hi);
	}
}

int Quick::Partition(int lo, int hi){

	int pivot = A[lo];
	int left = lo;
	
	for(int i = lo + 1; i <= hi; i++){
		comparisons += 2;
		if(A[i] < pivot){
			left++;
			int k = A[i];
			A[i] = A[left];
			A[left] = k;
		}
	}
	comparisons++;
	int k = A[left];
	A[left] = A[lo];
	A[lo] = k;
	
	return left;
	
}


Weird because I'm never deleting anything?
toum (353)
Does Q.Build() copy the content of x, or only the pointer ?
dfith (6)
Just the pointer. Also, the same pointer is used for implementations of mergesort, heapsort, and insertion sort in the same program (with mergesort and insertion sort copying the pointer).
Topic archived. No new replies allowed.