Why is this segment faulting?

The program runs and everything but for values in the list more than 100 it segment faults... The purpose of this program is to run Insertionsort only if the list size is less than the threshold; for all other sizes, the program will run both mergesort and quicksort otherwise. Also, the number of comparisons made by the sorting algorithms will be displayed. Any help would be appreciated.

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
235
#include <iostream>
   using namespace std;
   int icount = 0;
   int mcount = 0;
   int qcount = 0;
   
void insertionSort(int x[],int length) {
  int key,i;
  for(int j=1;j<length;j++) {
     key=x[j];
     i=j-1;
     while(x[i]>key && i>=0) {
	    x[i+1]=x[i];
		i--;
     }
     x[i+1]=key;
     icount++;
  }
}   
   
   
void merge(int a[], int Low, int Mid, int High);

void mergeSort(int a[], int Low, int High) {
     int Mid;
          
     if(Low < High) {
     Mid = (Low + High)/2;
     
     mergeSort(a, Low, Mid); 
     mergeSort(a, Mid+1, High);
     merge(a, Low, Mid, High);
     }
}


void merge(int a[], int Low, int Mid, int High) {
     int h = Low;
     int i = Low;
     int j = Mid+1;
     int b[100];
     int k;
     
     while( (h<=Mid) && (j<=High) ) 
     {
            if(a[h]<=a[j]) 
            {
                b[i]=a[h];
                h++;
                mcount++;
            }
            else
            {
                b[i]=a[j];
                j++;
                mcount++;
            }
            i++;
     }
     
     if(h>Mid) 
     {
            for(k = j; k<=High; k++)
            {
                  b[i] = a[k];
                  i++;
            }
            mcount++;
     }
     
     else
     {
            for( k = h; k<=Mid; k++)
            {
                 b[i] = a[k];
                 i++;
            }
            mcount++;
     }
     
     for(k=Low; k<=High; k++)
     {
            a[k] = b[k];
     }
}   
   
void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];
 
      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
                  qcount++;
            while (arr[j] > pivot)
                  j--;
                  qcount++;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
                  qcount++;
            }
      };
 
      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}   
   

int main() {
	srand(time(NULL));
	char keepGoing = 'y';

	while (keepGoing=='y') {


	// Collect info from user //

	   int thresholdValue;
	   int sizeOfList;
	   int autoList;
	   char displayList;
	   char comp;
	   cout << "" << endl;
	   cout << "Welcome to the Group 13's Sorting Program" << endl << endl;
	   cout << "This program will sort your lists using three different" <<
			"sorting algorithms dependent on the amount of items: Merge Sort," << 
			" QuickSort, and Insertion Sort."<< endl << endl;
	   cout << "To begin, please enter your threshold value: ";
	   cin >> thresholdValue;
	   cout << endl << "Please enter the size of your list: ";
	   cin >> sizeOfList;
	   int list_Values[sizeOfList];
	   int list_Values2[sizeOfList];
	   if (sizeOfList<=100) {
		cout << endl << "Would you like this list to be entered manually (Enter 0) or " <<
			"generated randomly by this program (Enter 1)?: ";
		cin >> autoList;
			if (autoList==0) {
				int counter = 0;
				cout << endl << "Please enter your values one line at a time." << endl;
				while (counter < sizeOfList) {
					cin >> list_Values[counter];
					list_Values2[counter] = list_Values[counter];
					counter++;
				}
			}
			if (autoList==1) {
				cout << endl << "Would you like the program to display the unsorted list? (y/n): ";
				cin >> displayList;
				if (displayList == 'y') {
                    cout << endl;
					for (int i=0; i<sizeOfList; i++) {
						list_Values[i] = (rand()%100)+1;
						list_Values2[i] = list_Values[i];
						cout << list_Values[i] << ", ";
					}
					cout << endl;
				}
				if (displayList == 'n') {
					for (int i=0; i<sizeOfList; i++) {
						list_Values[i] = (rand()%100)+1;
						list_Values2[i] = list_Values[i];
					}
				}
			}
		
		}
	   if (sizeOfList>100) {
			cout << endl << "The unsorted list will be randomly generated and not displayed." << endl;
			for (int i=0; i<sizeOfList; i++) {
				list_Values[i] = (rand()%100)+1;
				list_Values2[i] = list_Values[i];
			}
	   }
	   
	    cout << endl << "Would you like to see the number of comparisons made once sorted? (y/n)" << endl;
        cin >> comp;

	// Done collecting info from user //

	// Begin sorting //

 
		if (sizeOfList <= thresholdValue) {
			cout << endl << "Using Insertion Sort";
			insertionSort(list_Values,sizeOfList);
			cout << endl;
			for (int i=0; i<sizeOfList; i++) {
				cout << list_Values[i] << ", ";
			}
			cout << endl;
			if(comp == 'y') cout << "Number of comparisons: " << icount << endl;
		}
		
		
		else {
		
			// Sort using Quicksort & Mergesort, use the second list (list_Values2) that we stored since the
			// original will be altered.
			quickSort(list_Values,0, sizeOfList);
			mergeSort(list_Values2,0,sizeOfList);
			
		//	if (displayList == 'y') {
				cout << endl << "Sorted using QuickSort" << endl;
				for (int i=0; i<sizeOfList; i++) {
					cout << list_Values[i] << ", ";
                }
	            cout << endl;
				if(comp == 'y') cout << "Number of comparisons: " << qcount << endl;
				cout << endl << "Sorted using MergeSort" << endl;
				for (int i=0; i<sizeOfList; i++) {
					cout << list_Values2[i] << ", ";
				}
				cout << endl;
				if(comp == 'y') cout << "Number of comparisons: " << mcount << endl;
			//}
		}

	   cout << endl <<  "Would you like to sort another list? (y/n): ";
	   cin >> keepGoing;
	   
	}
	system("pause");
	return 0;
}
Topic archived. No new replies allowed.