C++

Forum

 
 
Segmentation fault problem

GreyOwl (23)
Hello I am recieving segmentation faults.
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
 
#include <iostream>
#include <iomanip>
#include <ctime>
#include <cstdlib>
using namespace std;
const int NUM_SIZES = 5;
typedef int DataType;
int indexOfLargest(const DataType[],
                   const int);
void swap(DataType&,
          DataType&);
void partition(DataType theArray[],int first, int last, int& pivotIndex);
void merge(DataType theAray[],int first,int mid, int last);
void selectionSort(DataType[],
                   const int);
//BubbleSort
void bubbleSort(DataType[],const int);
//InsertionSort
void insertionSort(DataType[],const int);
//MergeSort
void mergeSort(DataType[],int,int);
//QuickSort
void quickSort(DataType[],int,int);
//ShellSort
void shellSort(DataType[],int);
void printResults(int[][NUM_SIZES]);
enum SortType {SELECTION,
               BUBBLE,
               INSERTION,
               MERGE,
               QUICK,
               SHELL};
int main() {
   cout << "clockTicksPerSec = "
        << CLOCKS_PER_SEC
        << endl
        << endl;
// Seed the random number generator with the current time
   srand( (unsigned int)time(0) );

   const int SIZES[NUM_SIZES] = {10000,   //  10K
                                 20000,   //  20K
                                 40000,   //  40K
                                 80000,   //  80K
                                 160000}; // 160K

   clock_t startTime, endTime;

   int results[SHELL + 1][NUM_SIZES] = {0};

   for (int num = 0; num < NUM_SIZES; ++num) {

      // Main data to use in each sort routine
      DataType* dataArray = new int[SIZES[num]];

      // This array will be used to set 'dataArray' back to unsorted
      // state after each sort routine has finished with it
      DataType* backupArray = new int[SIZES[num]];

      // Generate array of random data (and its backup)
      for (int i = 0; i < SIZES[num]; ++i) {
         DataType randomNumber = rand() % SIZES[num] + 1;
         dataArray[i] = randomNumber;
         backupArray[i] = randomNumber;
      }
      ////////SELECTION///////////////////////////////////////////
      // Get the time just before 'selectionSort' starts
      startTime = clock();
      // Sort the array
      selectionSort(dataArray, SIZES[num]);
      // Get the time just after 'selectionSort' finishes
      endTime = clock();
      // Store the elapsed time required to selection sort an array
      // with SIZES[num] items in it.
      results[SELECTION][num] = endTime - startTime;
      // Restore the original (unsorted) data in 'dataArray'
      for (int i = 0; i < SIZES[num]; ++i) {
         dataArray[i] = backupArray[i];
      }
      /////////////////////////////////////////////////////////////
      ////////BUBBLESORT//////////////////////////////////////////
      startTime = clock();
      bubbleSort(dataArray,SIZES[num]);
      endTime = clock();
      results[BUBBLE][num] = endTime - startTime;
      for (int i = 0; i < SIZES[num]; ++i) {
         dataArray[i] = backupArray[i];
      }
      ////////////////////////////////////////////////////////////
      /////////INSERTION//////////////////////////////////////////
      startTime = clock();
      insertionSort(dataArray,SIZES[num]);
      endTime = clock();
      results[INSERTION][num] = endTime - startTime;
      for (int i = 0; i < SIZES[num]; ++i) {
         dataArray[i] = backupArray[i];
      }
      ////////////////////////////////////////////////////////////
      ////////MERGE///////////////////////////////////////////////
      startTime = clock();
      mergeSort(dataArray,0,4);
      endTime = clock();
      results[MERGE][num] = endTime - startTime;
      for (int i = 0; i < SIZES[num]; ++i) {
          dataArray[i] = backupArray[i];
      }
      ////////////////////////////////////////////////////////////
      ////////QUICK///////////////////////////////////////////////
      startTime = clock();
      int first = dataArray[0];
      int last = dataArray[(SIZES[num] - 1)];
      quickSort(dataArray,first,last);
      endTime = clock();
      results[QUICK][num] = endTime - startTime;
      for (int i = 0; i < SIZES[num]; ++i) {
         dataArray[i] = backupArray[i];
      }
      ////////////////////////////////////////////////////////////
      ////////SHELL///////////////////////////////////////////////
      startTime = clock();
      shellSort(dataArray,SIZES[num]);
      endTime = clock();
      results[SHELL][num] = endTime - startTime;
      for (int i = 0; i < SIZES[num]; ++i) {
         dataArray[i] = backupArray[i];
      }
      ////////////////////////////////////////////////////////////
      // Release dynamic memory used
      delete [] dataArray;
      delete [] backupArray;
   }
   // Output the results of all runs
   printResults(results);
   return 0;
}
int indexOfLargest(const DataType theArray[],
                   const int size) {
   int indexSoFar = 0;

   for (int currentIndex = 1; currentIndex < size; ++currentIndex) {
      if (theArray[currentIndex] > theArray[indexSoFar]) {
         indexSoFar = currentIndex;
      }
   }
   return indexSoFar;
}

void swap(DataType& x,
          DataType& y) {
   DataType temp = x;

   x = y;
   y = temp;
}

       void selectionSort(DataType theArray[],
                        const int n) {

        for (int last = n - 1; last >= 1; --last) {
        int largest = indexOfLargest(theArray, last + 1);

        swap(theArray[largest], theArray[last]);
        }
        }

        void bubbleSort(DataType theArray[], const int n)
        {
        bool sorted = false;
        int pass;
                for (pass = 1; (pass < n) && !sorted; ++pass)
                {
                sorted = true;
                   for (int index = 0; index < n-pass; ++index)
                   {
                   int nextIndex = index + 1;
                      if (theArray[index] > theArray[nextIndex])
                      {
                      swap(theArray[index], theArray[nextIndex]);
                      sorted = false;
                      }
                   }
                }
        }

        void insertionSort(DataType theArray[], const int n)
        {
          for (int unsorted = 1; unsorted < n; ++unsorted)
          {
          DataType nextItem = theArray[unsorted];
          int loc = unsorted;
             for (;(loc > 0) && (theArray[loc - 1] > nextItem);--loc)
                theArray[loc] = theArray[loc - 1];
                theArray[loc] = nextItem;
        }

        }
        void merge(DataType theArray[],int first,int mid, int last)
        {
        DataType tempArray[5];
        int first1 = first;
        int last1 = mid;
        int first2 = mid + 1;
        int last2 = last;
        int index = first1;
        for (;(first1 <= last1) && (first2 <= last2); ++index)
        {
          if (theArray[first1] < theArray[first2])
          { tempArray[index] = theArray[first1];
            ++first1;
          }
          else
          {  tempArray[index] = theArray[first2];
             ++first2;
          }
        }
        for (; first1 <= last1; ++first1, ++index)
           tempArray[index] = theArray[first1];
        for (; first2 <= last2; ++first2, ++index)
           tempArray[index] = theArray[first2];
        for (index = first;index <= last; ++index)
           theArray[index] = tempArray[index];
        }

        void mergeSort(DataType theArray[],int first,int last)
        {
          if ( first < last)
          {
          int mid = 2;
          mergeSort(theArray,first,mid);
          mergeSort(theArray,3,last);
          merge(theArray,first,mid,last);
          }
        }

The seg fault apparently occurs within this portion of the code
Last edited on
Zaita (2770)
Please wrap your code in [code] tags and provide more information about where the segmentation fault is occurring.
GreyOwl (23)
I am sorry I am brand new to this website what do you mean by tags? And also the problem is I can't find where it is occuring!
Zaita (2770)
Writing [code] and [ /code] around your code will syntax highlight it for us. Have you tried putting in debug statements to see how far execution progresses or running it through a debugger to isolate the crash?
GreyOwl (23)
Okay I inserted the tags, sorry if it is messy I had to take out a ton of whitespace, I am currently trying use the debugging methods I have never used them before I will see what I can come up with
Last edited on
GreyOwl (23)
Wow using gdb was extremely helpful it gave the output: 
1
2
3
4
5
6
7
8
9
10
11
 
Reading symbols from /home/volq/35/nordx085/cs1521/labs/lab6/lab6...done.
(gdb) run
Starting program: /home/volq/35/nordx085/cs1521/labs/lab6/lab6
clockTicksPerSec = 1000000


Program received signal SIGSEGV, Segmentation fault.
0x08049287 in mergeSort (theArray=0x804b008, first=0, last=2) at main.cpp:263
263               mergeSort(theArray,first,mid);
(gdb)

okay so I will take a look at this because the line numbering is off compared to the original source code in linux

okay so it is in line 151 in this code but I really don't know what is wrong with it
Last edited on
ne555 (10692)
.oi: please indent your code properly.

Try to provide a minimal snip that does compile
GreyOwl (23)
Things would be indented properly but I had to unindent things so all this can fit because there is a character limit. Everything else compiles fine except there is an error at run time with the output:
bulldog:~/cs1521/labs/lab6% ./lab6
1
2
3
 
clockTicksPerSec = 1000000

Segmentation fault

bulldog:~/cs1521/labs/lab6%

Using gdb the seg fault apparently occurs on line 151 and I don't find anything wrong with it, if no one knows what is wrong then thanks anyways
TheIdeasMan (6817)
Instead of massively editing your code to make it unreadable, do one of the following:

1. Split it up over several posts. IMO preferable.
2. Post it one of the online dropbox sites.

With the code tags, you can put a firstline=257 after code in the opening code tag so the line number start at 257 in this case - or whatever number you like. That way you can have the lines numbers the same as your code. If posting all the code - then post all of it & the line numbers will be fine.

257
258
259
260
261
262
263
264
265
 
void mergeSort(DataType theArray[],int first,int last)
        {
          if ( first < last)
          {
          int mid = 2;
          mergeSort(theArray,first,mid);
          mergeSort(theArray,mid+1,last);
          merge(theArray,first,mid,last);
          }}
Last edited on
ne555 (10692)
Your snip does not compile.
Missing prototypes (and headers), ¿wtf is DataType?, extra } in line 187

> because there is a character limit
_ Minimize the test case
_ separate the code in several posts (logically)
_ Use an external paste site (by instance codepad.org or github)
TheIdeasMan (6817)
with gdb, you can do a bt command (backtrace) to see what the values of the variables were when it segfaulted.

There is a gdb tutorial in the articles section of this site.
GreyOwl (23)
Yes it did not compile because that was not the full code. I have edited the original to include all original code up until the function that gdb says is causing the seg fault which is specifically line 263, but I do not see the issue. Hopefully now things should be easier to see. Any help would be appreciated!
Last edited on
ne555 (10692)
1
2
3
4
5
6
7
8
9
10
 
void mergeSort (DataType theArray[], int first, int last)
{
	if (first < last) //true
	{
		int mid = 2; //¿?
		mergeSort (theArray, first, mid);
		mergeSort (theArray, 3, last); //¿?
		merge (theArray, first, mid, last);
	}
}
If you perform a backtrace you'll see the call stack.
You've got stack overflow, because of infinite recursion.

> which is specifically line 263
.oicai: your snips stops at line 234
GreyOwl (23)
okay I think I fixed the other section in mergeSort. Because it runs now. But I receiving 
1
2
3
4
5
6
 
0x08049075 in bubbleSort (theArray=0xb7d07008, n=80000) at main.cpp:204
204                           swap(theArray[index], theArray[nextIndex]);
(gdb) backtrace
#0  0x08049075 in bubbleSort (theArray=0xb7d07008, n=80000) at main.cpp:204
#1  0x08048b6c in main () at main.cpp:98
(gdb)

which corresponds to 
1
2
3
4
 
  if (theArray[index] > theArray[nextIndex])
                      {
                      swap(theArray[index], theArray[nextIndex]);
                      sorted = false;

specifically the swap function.
At runtime I do seem to be in infinite recursion as the program never stops now instead of giving me a seg fault
Last edited on
ne555 (10692)
From inside the debugger, when it seg fault
> print index
> print nextIndex

Keep it mind that your algorithms are O(n^2), so it would take a while.
Also, update your code.
Last edited on
GreyOwl (23)
Okay so I fixed every error. But now I do not get any results. I will upload the code and the output but it could take a few posts.
code: http://pastebin.com/BPRJ6gQh
output:
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
clockTicksPerSec = 1000000

SelectionSort
BubbleSort
InsertionSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
QuickSort
ChoosePivot
QuickSort
QuickSort
ChoosePivot
QuickSort
QuickSort
ShellSort
SelectionSort
BubbleSort
InsertionSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
QuickSort
ChoosePivot
QuickSort
QuickSort
ChoosePivot
QuickSort
ChoosePivot
QuickSort
QuickSort
QuickSort
ShellSort
SelectionSort
BubbleSort
InsertionSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
QuickSort
ChoosePivot
QuickSort
ChoosePivot
QuickSort
ChoosePivot
QuickSort
QuickSort
QuickSort
QuickSort
ShellSort
SelectionSort
BubbleSort
InsertionSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
QuickSort
ChoosePivot
QuickSort
ChoosePivot
QuickSort
QuickSort
QuickSort
ShellSort
SelectionSort
BubbleSort
InsertionSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
MergeSort
QuickSort
ChoosePivot
QuickSort
ChoosePivot
QuickSort
ChoosePivot
QuickSort
ChoosePivot
QuickSort
QuickSort
QuickSort
QuickSort
QuickSort
ShellSort
Selection sort
   N   Time(ms)
 10000 0
 20000 0
 40000 0
 80000 0
160000 10000

Bubble sort
   N   Time(ms)
 10000 0
 20000 0
 40000 0
 80000 0
160000 0

Insertion sort
   N   Time(ms)
 10000 0
 20000 0
 40000 0
 80000 0
160000 0

Merge sort
   N   Time(ms)
 10000 0
 20000 0
 40000 0
 80000 0
160000 0

Quick sort
   N   Time(ms)
 10000 0
 20000 0
 40000 0
 80000 0
160000 0

Shell sort
   N   Time(ms)
 10000 0
 20000 0
 40000 0
 80000 0
160000 0

as you can see there are no times in the time catagort, also things are being called a very large amount of times I am not sure if that is normal.
ne555 (10692)
selectionSort(dataArray,5); ¿5? ¿why 5?
It is too small to measure.

You've got several {Merge,Quick}sort because the function is recursive
GreyOwl (23)
Well I placed 5 there because, according to the algorithm I'm following, selection sort takes in the array and the arrays length, which I believe to be five. I am also following two different algorithms from my textbook very closely when it comes to merge and quicksort so I don't understand why those are not right. Any suggestions for their implementation?
Topic archived. No new replies allowed.