Why is this seg faulting????

This is a discussion on Why is this seg faulting???? within the C++ Programming forums, part of the General Programming Boards category; The program runs and everything but for values in the list more than 100 it segment faults... The purpose of ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    10

    Why is this seg 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. Is it one of the sorting algorithms????

    Code:
    #include <iostream>
    #include <ctime>
       using namespace std;
       int icount = 0;
       int mcount = 0;
       int qcount = 0;
       
    // Merge prototype
    void merge(int a[], int Low, int Mid, int High);
       
    // Insertion sort method
    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--;
            icount++;
         }
         x[i+1]=key;
      }
    }   
       
      
    
    
    // Mergsort method
    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);
         }
    }
    
    
    // Merge method
    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];
         }
    }   
    
    
    // QuickSort Method   
    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() {
        int validationCheck = 0; // Check input to make sure it matches.
        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]; // Two arrays so that sorting algorithms can be shown side-by-side.
           if (sizeOfList<=100) {
                while (validationCheck==0) {
                    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) || (autoList == 1) ) validationCheck = 1;
                }
                validationCheck = 0; // Reset validation
                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) {
                    while (validationCheck==0) {
                        cout << endl << "Would you like the program to display the unsorted list? (y/n): ";
                        cin >> displayList;
                        if ( (displayList == 'y') || (displayList == 'n') ) validationCheck = 1;
                    }
                    validationCheck = 0; // Reset Validation check.
                    if (displayList == 'y') {
                        cout << endl;
                        for (int i=0; i<sizeOfList; i++) {
                            list_Values[i] = (rand()0)+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()0)+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()0)+1;
                    list_Values2[i] = list_Values[i];
                }
           }
            while (validationCheck==0) {
                cout << endl << "Would you like to see the number of comparisons made once sorted? (y/n)" << endl;
                cin >> comp;
                if ( (comp == 'y') || (comp == 'n') ) validationCheck = 1;
            }
            validationCheck = 0; // Reset validationCheck;
            
    
    
        // 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);
                
                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;
            }
            while (validationCheck==0) {
               cout << endl <<  "Would you like to sort another list? (y/n): ";
               cin >> keepGoing;
               if ( (keepGoing == 'y') || (keepGoing == 'n') ) validationCheck = 1;
           }
           validationCheck = 0; // Reset validation;
        }
        return 0;
    }

  2. #2
    Registered User
    Join Date
    Oct 2006
    Posts
    2,487
    it probably has something to do with the statically sized array you define in merge().

    also, it's good to name your variables with meaningful names. single letters are rarely meaningful to anyone but you, and even you could eventually forget what variable b in function foo() represents. one of the few exceptions to this is in loop counters. I (and many others) name my for loop counter "i" if it's an int, for example.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. get id of faulting thread
    By Elkvis in forum Linux Programming
    Replies: 4
    Last Post: 04-27-2009, 03:45 PM
  2. Get faulting address on SIGSEGV
    By kruemelmonster in forum Linux Programming
    Replies: 12
    Last Post: 04-21-2009, 10:29 PM
  3. seg faulting
    By Xyruul in forum C Programming
    Replies: 14
    Last Post: 04-18-2007, 01:44 PM
  4. seg-faulting w/linked list but dont know why
    By aciarlillo in forum C++ Programming
    Replies: 1
    Last Post: 05-29-2005, 03:53 PM
  5. pointers seg faulting
    By snareguy in forum C Programming
    Replies: 1
    Last Post: 03-21-2004, 11:33 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21