hello,

I am running a merge sort routine on an array of numbers. My intention is not to output the sorted array but to reorder the indices of the array so that they reflect the sorted order (descending). For example, if the array were {2, 7, 4}, my indices would be {1,2,0}. Thus I need to update the identity map {0,1,2} to {1,2,0}. I store this map as a vector of ints. I feed the array of numbers and an iterator pointing to the first element of the map-vector as well as the array-size to the merge-sort subroutine. I first call mergeSort(...) which calls m_sort(....) which calls itself and merge(...).

Identifiers used and their meaning:
numbers: array of numbers to sort
fn : map array (doesn't appear in code)
fn_ptr: iterator on venctor<int> that points to the first element of the
map vector
left : first index of range to sort
right: last index of range to sort

----

``````void merge(double numbers[], vector<int>::iterator fn_ptr, int left, int mid, int right);

void mergeSort(double numbers[],vector<int>::iterator fn_ptr, int array_size)
{
m_sort(numbers, fn_ptr, 0, array_size - 1);
}

void m_sort(double numbers[], vector<int>::iterator fn_ptr, int left, int right)
{
int mid;
vector<int>::iterator dum_ptr;

if (right > left)
{
mid = (right + left) / 2;

//recursive call to sort two contiguous subsets
m_sort(numbers, fn_ptr, left, mid);
m_sort(numbers, fn_ptr+mid-left+1, (mid+1), right);

//merge sorted subsets
merge(numbers, fn_ptr, fn_ptr+mid-left+1, left, (mid+1), right);
}
}

void merge(double numbers[], vector<int>::iterator fn_ptr_1, vector<int>::iterator fn_ptr_2, int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
int N_cp=sizeof(numbers);

vector<int> fn_dum(N_cp);
vector<int>::iterator dum_ptr=fn_ptr_1;

left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);

int left_dum=left;

while ((left <= left_end) && (mid <= right))
{
if (numbers[*fn_ptr_1] >= numbers[*fn_ptr_2])
{
fn_dum[tmp_pos] = *fn_ptr_1;
tmp_pos += 1;
left ++;
++fn_ptr_1;
}
else
{
fn_dum[tmp_pos] = *fn_ptr_2;
tmp_pos += 1;
mid += 1;
++fn_ptr_2;
}
}

while (left <= left_end)
{
fn_dum[tmp_pos] = *fn_ptr_1;
left += 1;
++fn_ptr_1;
tmp_pos += 1;
}
while (mid <= right)
{
fn_dum[tmp_pos] = *fn_ptr_2;
mid += 1;
++fn_ptr_2;
tmp_pos += 1;
}

//update fn using fn_dum

for (i=0; i < num_elements; i++)
{
*dum_ptr = fn_dum[left_dum];
left_dum++;
++dum_ptr;

}
fn_dum.clear();
cout << "End of merge." << endl;
cout << endl;

}``````

------

I call the mergeSort as

mergeSort(numbers, fn_ptr,array_size).

In the example above, numbers = {2,7,4}. I create fn={0,1,2} as a vector<int>, and then set fn_ptr=fn.begin(). Then, I call

mergeSort(numbers,fn_ptr,3).

Note that in any call, fn_ptr points to the value of fn at the first index in the range to be sorted.

In my implementation, array_size=100. I get the "glibc detected" error inside m_sort(numbers,fn_ptr,10,12), at the point where msort(.,.,10,11) has completed and msort(.,.,12,12) is about to be called.

Tara

Edited by peter_budo: Corecting closing code tag to [/code]

2
Contributors
4
Replies
5
Views
8 Years
Discussion Span
Last Post by tararengan

Line 30 is suspicious. sizeof(numbers) yields a size of a pointer to double.

Line 30 is suspicious. sizeof(numbers) yields a size of a pointer to double.

Is it? numbers is both an array identifier and a pointer to its first element, right? the sizeof() function uses the first interpretation I think.

You think wrong. As a function argument, numbers is a pointer. Try to print N_cp.

You think wrong. As a function argument, numbers is a pointer. Try to print N_cp.

Ok, you were right. Thanks very much. :-)

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.