C++

Forum

 
merge sort implementation problem

Jan 9, 2017 at 4:11pm
madeleine (5)
Hi. On lecture profesor did present us natural merge sort algorithm implementation in C++. Unfortunatelly the given code did not work in proper way. Probably I have missed something or have written down something wrong.

I was looking for this algorithm online and in books, but I found different algorithm for merge sort. The truth is that I don't really understand this algorithm so I'm not able to find where is mistake.

Could you please help my to find what is missing or mayby explain this verssion of merge sorting.

Thanks for your help in advance! 

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
 

//copy function 

  bool copy(int* t, int *i, int * tmp, int* ix, int nLast)
{
	t[(*i)++] = tmp[(*ix)++];
	if (*ix = nLast)
		return true;
	return tmp[*ix - 1] > tmp[*ix];
}

//copy series function

void CopySerie(int* t, int *i, int * tmp, int* ix, int nLast)

{
	bool bEnd = false;
	do{
		bEnd = copy(t, i, tmp, ix, nLast);
	} while (!bEnd);
}

void Merge(int* t, int nSize)
{

	int *tmp1 = (int*)malloc(sizeof(int));
	int *tmp2 = (int*)malloc(sizeof(int));

	int i = 0;
	int j = 0;
        int k = 0;

	//dividing 

		while (i < nSize){

			while (i < nSize - 1 && t[i] <= t[i + 1])
				tmp1[j++] = t[i++];
			tmp1[j++] = t[i++];

			while (i < nSize - 1 && t[i] <= t[i + 1])				while (i<nSize - 1 && t[i] <= t[i+1])

				tmp2[k++] = t[i++];

			if (i < nSize)
				tmp2[k++] = t[i++];
		}

		int nLast1 = j; //end of serie in tmp 1
		int nLast2 = k; //end of serie in tmp 2

//merging and counting series

		int nSerie = 0;
		i = j = k = 0;

//transfering data from temporary arrays to main array

		while ((j < nLast1) && (k < nLast2))
		{
		bool bEndSerie = false;

		while (!bEndSerie)
		{
			if (tmp1[j] <= tmp2[k])
			{
				bEndSerie = copy(t, &i, tmp1, &j,nLast1);
				if (bEndSerie)
					CopySerie(t, &i, tmp2, &k, nLast2);
				}
				else
				{
				bEndSerie = copy(t, &i, tmp2, &k, nLast2);
				if (bEndSerie)
					CopySerie(t, &i, tmp1, &j, nLast1);
				}
			}

			nSerie++;
		}

		//while ((j<nLast1)&&(k<nLast2))
		while (j < nLast1)
		{ 
			CopySerie(t, &i, tmp1, &j, nLast1);
			nSerie++;
		}
		while (k < nLast2)
		{
                        CopySerie(t, &i, tmp2, &k, nLast2);
			nSerie++;
		}

	

}
Jan 9, 2017 at 4:45pm
AbstractionAnon (6954)
The most obvious thing that is wrong is that at lines 26-27 you are allocating a single int to tmp1 and tmp2. Yet in your loops, you're indexing through tmp1 and tmp2 as if they had been allocated with size nSize.
Jan 9, 2017 at 4:53pm
madeleine (5)
of course.Thanks for this remark. I corrected it:
1
2
 
int *tmp1 = (int*)malloc(sizeof(int)*nSize);
int *tmp2 = (int*)malloc(sizeof(int)*nSize);


However there was probably not only one mistake. Still does not work properly.
Last edited on Jan 9, 2017 at 4:53pm
Jan 9, 2017 at 8:07pm
cire (8284)
Line 7 is assignment. You probably meant to use comparison (and it is likely your compiler generates a warning for that line.)
Jan 10, 2017 at 10:16am
madeleine (5)
Yes. It is also right. I'll correct it.
However my main problem is that this program does not sort the table, ale I don't know how, because I have nothing but this program and I don't really know how it should work. Ihis merge sort is different then the standard one presented in books.
Topic archived. No new replies allowed.