C++

Forum

 
 
Using Merge Sort With Struct Array

skinny2741 (8)
Help me.

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
 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

typedef struct  {
    string tarih;
    float deger;
}divide_and_conq_dt;



void merge_sort(divide_and_conq_dt[],int,int);
void merge(divide_and_conq_dt[], int , int , int );



int main()
{
    divide_and_conq_dt dizi[5];
    int begin = 0;
    int end = 5;
    


    for (int i = 0; i < 5; i++) {
        cout << "tarih gir" << endl;
        cin >> dizi[i].tarih;
        cout << "deger gir" << endl;
        cin >> dizi[i].deger;
    }

    merge_sort(dizi,begin,end);
    for (int i = 0; i < 5; i++) {
   
        cout << "tarih:" << dizi[i].tarih << "---" << "deger:" << dizi[i].deger << endl;
    }
    
}


static void merge_sort(divide_and_conq_dt dizi[],int begin,int end) {
    int middle = 0;
    if (begin < end) {
       
        middle = (begin + end)  / 2;
        merge_sort(dizi, begin, middle);
        merge_sort(dizi, middle + 1, end);
        merge(dizi,begin, middle, end);
    }

}

void merge(divide_and_conq_dt dizi[], int begin, int middle, int end) {

    int i = 0;
    int left = begin;
    int right = middle + 1;
    int combined = begin;
    divide_and_conq_dt temp[5];

    while (left<=middle&&right<=end) {
        if (dizi[left].deger <= dizi[right].deger) {
            temp[combined++] = dizi[left++];
        }
        else
        {
            temp[combined++] = dizi[right++];
        }
    }

    if (left == middle + 1) {
        while (right <= end) {
            temp[combined++] = dizi[right++];
        }
    }
    else {
        while (left <= middle) {
            temp[combined++] = dizi[left++];
        }
    }

    for (i = end; i <= end; i++) {
        dizi[i] = temp[i];
    }





   


}
Last edited on
seeplus (6597)
... and the issue is?
skinny2741 (8)
At point 0x789E368E (vcruntime140d.dll), an exception occurred on Algoritma_Analysis_Momework.exe: 0xC0000005: Read access violation at location 0xE9EB1E83.
ElusiveTau (157)
skinny2741 wrote:
Help me.

It's 6:52 AM as I'm typing, there's snow outside, and I'm having my first cup of coffee (hazelnut!) since I've awoken. Feel very privileged and thankful to have woken up so peacefully, given the state of the world. I like ramping up in the morning this way. So you see, dear user, we're not all robots whose solitary directive is to infer your homework problems and fix them. Do us a solid :-)?

'tarih' and 'deger' (value) are Turkish, according to google. Maybe the user doesn't speak English well enough to explain the problem. But on the off chance he can understand English, he needs to put more effort in explaining what is wrong.
Last edited on
skinny2741 (8)
Actually, I don't know what the problem is. That's why I asked for help. "tarih" and " deger" just variable. By the way, I'm sorry to bother you.
seeplus (6597)
Probably the easiest way to find the problem is to use the debugger. Trace through the code using the debugger watching the variables. When execution deviates from that expected, then you found an issue.
skinny2741 (8)
thank you seeplus. I will try.
Last edited on
ElusiveTau (157)
Compiler complains:
In function 'void merge_sort(divide_and_conq_dt*, int, int)':
42:67: error: 'void merge_sort(divide_and_conq_dt*, int, int)' was declared 'extern' and later 'static' [-fpermissive]
13:6: note: previous declaration of 'void merge_sort(divide_and_conq_dt*, int, int)'


So we fix the syntax error
1
2
3
4
5
6
7
8
9
10
11
 
static void merge_sort(divide_and_conq_dt dizi[],int begin,int end) {
    int middle = 0;
    if (begin < end) {
       
        middle = (begin + end)  / 2;
        merge_sort(dizi, begin, middle);
        merge_sort(dizi, middle + 1, end);
        merge(dizi,begin, middle, end);
    }

}


When I run the code (after minor syntax fixes) in Visual Studios, I get a memory-access violation.

This might be a part of the problem. There are 5 elements to sort so the end index should be 4 (in general, one less than the number of elements).
 
 
merge_sort(dizi, begin, end end-1);


This might be a part of the problem, where you're copying the temporary (sorted) subarray back into the (unsorted) original array. Maybe a careless mistake.
1
2
3
4
 
    for (i = end begin; i <= end; i++) {
        dizi[i] = temp[i];
    }
}


Seems to sort fine after that for these test cases:

input1.txt 
1
2
3
4
5
6
7
8
9
10
 
five
5
four
4
three
3
two
2
one
1



input2.txt 
1
2
3
4
5
6
7
8
9
10
 
five
1
four
-3
three
4
two
2
one
5


Last edited on
Topic archived. No new replies allowed.