Segmentation fault

[JaksLax]

I am getting a Segmentation fault when I run my code. It is happening right now when the 100,000th array location is being populated. But it has been at different spots when I ran it before. Any ideas??

/** 
* @author Jason Mejak 
* 
* This program uses the implementation of the hybrid QuickSort/InsertionSort
* and uses a large array to test the speed of the sorts 
* 
* @date 5/17/07 
*/ 

#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;


/**
 * Sorts the items in an array into ascending order.
 *
 * @pre theArray is an array of n items.
 *
 * @post theArray is sorted into ascending order; n is unchanged.
 *
 * @param theArray The given array
 *
 * @param n The size of the array
 */

void InsertionSort(int theArray[], int n){

  for(int unsorted = 1; unsorted < n; ++unsorted){

    int nextItem = theArray[unsorted];
    int loc = unsorted;

    for(;(loc > 0) && (theArray[loc-1] > nextItem); --loc){

      //Shift theArray[loc-1] to the right
      theArray[loc] = theArray[loc - 1];

    }

    //insert nextItem into Sorted region
    theArray[loc] = nextItem;

  }

}

/**
 * Partions an array for quicksort.
 *
 * @pre theArray[fisrt..last] is and array; first <= last.
 *
 * @post Partions theAray[first..last] such that:
 *    S1 = theArray[first..pivotIndex-1] < pivot
 *         theArray[pivotIndex]         == pivot
 *    S2 = theArray[pivotIndex+1..last] >= pivot
 *
 * @param d The given array.
 *
 * @param left The first element to consider in theArray
 *
 * @param right The last elem to consider in theArray.
 */

int Partition( int d[], int left, int right){

  int val =d;
  int lm = left-1;
  int rm = right+1;

    for(;;) {
      do
        rm--;
      while (d[rm] > val);
        
      do 
        lm++;
      while( d[lm] < val);

      if(lm < rm) {
        int tempr = d[rm];
        d[rm] = d[lm];
        d[lm] = tempr;
      }
      else 
        return rm;
    }
}

void QuickSort (int A[], int F, int L){

  int PivotIndex;

  if (F < L){

    //is this a small region?
    if ((L - F) < 50){

      //yes...so use InsertionSort
      InsertionSort (A, L);

    }else{

      //no...do normal QuickSort
      Partition (A, F, L);
      QuickSort (A, F, PivotIndex-1);
      QuickSort (A, PivotIndex+1, L);
      
    }
  }
}

int main(){

  int randomArray[100000];

  int cOff = 50;

  for(int i = 0; i < 100000; i++){

    randomArray[i] = rand();
    cout<< i << "\n";

  }

  QuickSort(randomArray, 0, 200000);


}

[Lerner]

I suspect you're either reading/writing out of bounds on one of your arrrays or you have overfilled the stack. Since the latter is quiet easy to check, I'd check that first. To do it, declare randomArray on the heap using dynamic memory allocation rather than on the stack using static memory allocation.

[JaksLax]

Here is what I changed

int main(){

  int * randomArray;
  randomArray = new int [100000];

  int cOff = 50;

  for(int i = 0; i < 100000; i++){

    randomArray[i] = rand();
    cout<< i << " : " << randomArray[i] << "\n";

  }

  QuickSort(randomArray, 0, 100000);


}

But I am still getting this when I run the program

99992 : 884310116
99993 : 2013282372
99994 : 1484484072
99995 : 258787258
99996 : 783060031
99997 : 1110152201
99998 : 990117071
99999 : 46831694
Segmentation fault

So still when it gets to the last spot it faults. Any other ideas??

[Lerner]

when i == 99999 it is the 100,000 item. I'd put a line like cout << "array filled" << endl; before the call to QuickSort() and rerun the program. If you see the message "array filled" on the screen before the segmentation fault occurs then the problem is out in one of the other functions somewhere. Throw in a bunch of output messages or serially move a message like cout << "here" << endl; throughout the various functions to try to narrow down where the problem is happening.

[Salem]

> Partition (A, F, L);
This returns a value, which you ignore.

> QuickSort (A, F, PivotIndex-1);
This uses a value of PivotIndex, which is uninitialised.

> InsertionSort (A, L);
Here you try to sort the whole array, not just a fragment from F to L