C++

Forum

 
Merge Sort

bathach95 (25)
I code the merge function like this but when I test,there's an error trigged breakpoint at the show() func, but I don't know why.
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
 
  void show(int a[], int n)
{
	for (int i = 0; i < n; i++)
		cout << a[i] << ' ';
}
void merge(int array1[], int first,int last)
{
	int* temp = new int[];
	int	mid = (first + last) / 2;
	int i1 = 0;
	int i2 = first;
	int i3 = mid + 1;
	while(i2 <= mid && i3 <= last)
	{
		if	(array1[i2] < array1[i3])
			temp[i1++] = array1[i2++];
		else	temp[i1++] = array1[i3++];
	}
	//load into	temp	the remaining elements of		array1;
	if (i2 > mid && i3 <= last)
	{
		for (i3; i3 <= last;)
			temp[i1++] = array1[i3++];
	}
	else if (i2 <= mid && i3 > last)
	{
		for (i2; i2 <= mid;)
			temp[i1++] = array1[i2++];
	}
	//load to	array1	the content of	temp;
	for (int i = 0; i <= last; i++)
		array1[i] = temp[i];
	show(array1, last + 1);
}
int main()
{
	int arr[] = { 1, 3, 6, 7, 0, 4, 8 };
	merge(arr, 0, 6);
	system("pause");
	return 0;
}
Last edited on
coder777 (8442)
Line 8 shouldn't compile. If it does it creates an array with the size 0. That means that each access to the array is out of bounds. Change it to:

int* temp = new int[last + 1];
bhalo (16)
hello, i have merge sort code, but yet to learn.
but bathach95's method looks much more simpler. whats difference between them?

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
 
// https://code.google.com/p/medicine-cpp/source/browse/trunk/cpp/sorting/SortingAlgorithms.cpp
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
void swap(std::vector<int> & data, int i, int j);
void print(std::vector<int> const & data);
void Merge(std::vector<int> & data, int lowl, int highl, int lowr, int highr);
void MergeSort(std::vector<int> & data, int low, int high);



int main()
{
    int a[] = {5, 6, 1, 2, 0, 8, -1, -2, 8, 0};
    std::vector<int> data(a, a + sizeof(a)/sizeof(int));

    MergeSort(data, 0, data.size()-1);
    print(data);
   
    return 0;
}

void swap(std::vector<int> & data, int i, int j)
{
    int tmp = data[i];
    data[i] = data[j];
    data[j] = tmp;
}

void print(std::vector<int> const & data)
{
    std::vector<int>::const_iterator iter = data.begin();

    for (; iter != data.end(); ++iter)
    {
        cout << *iter << " ";
    }

    if (data.size() > 0)
    {
        cout << endl;
    }
}


void MergeSort(std::vector<int> & data, int low, int high)
{
    if (low >= high)
    {
        return;
    }
   
    int mid = low + (high-low)/2;

    MergeSort(data, low, mid);

    MergeSort(data, mid+1, high);

    Merge(data, low, mid, mid+1, high);
}

void Merge(std::vector<int> & data, int lowl, int highl, int lowr, int highr)
{
    int tmp_low = lowl;
    std::vector<int> tmp;
   
    while (lowl <= highl && lowr <= highr)
    {
        if (data[lowl] < data[lowr])
        {
            tmp.push_back(data[lowl++]);
        }
        else if (data[lowr] < data[lowl])
        {
            tmp.push_back(data[lowr++]);
        }
        else
        {
            tmp.push_back(data[lowl++]);
            tmp.push_back(data[lowr++]);
        }
    }

    while (lowl <= highl)
    {
        tmp.push_back(data[lowl++]);
    }

    while (lowr <= highr)
    {
        tmp.push_back(data[lowr++]);
    }

    std::vector<int>::const_iterator iter = tmp.begin();
   
    for(; iter != tmp.end(); ++iter)
    {
        data[tmp_low++] = *iter;
    }
}
coder777 (8442)
@bhalo
The merge functions are basically the same (count the loops) just written differently. You have addtitionally the MergeSort(...) function
Topic archived. No new replies allowed.