Any Help - Getting a segmentation fault

[code46]

Hello,

I wrote a quicksort program that will give me the execution time of the algorithm. I was running it for 1,000, 10,000, 100,000, 1,000,000, and 10,000,000 numbers.

Everything was going fine and then when I changed the amount of numbers it is sorting it gave me a segmentation fault error. I am new to this so I really do not know what that means or how to fix it.

Below is the code for reference for anybody who can help.

// quicksort.cpp

#include <algorithm> 
#include <assert.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

static int random(int ceiling) {
  return static_cast<int>((static_cast<float>(rand()) / RAND_MAX) * ceiling);
}

static void scramble(int a[], int aSize) {
  for (int i = 0; i < aSize; i++)
    std::swap(a[i], a[random(aSize)]);
}

static void makeScrambledArray(int a[], int size) {
  for (int i = 0; i < size; i++)
    a[i] = i;
  scramble (a, size);
}

// BEGIN-ALGORITHM
static int partition(int a[], int first, int last) {
  int pivot = a[first];
  int lastS1 = first;
  int firstUnknown = first + 1;
  while (firstUnknown <= last) {
    if (a[firstUnknown] < pivot) {
      lastS1++;
      std::swap(a[firstUnknown], a[lastS1]);
    }
    firstUnknown++;
  }
  std::swap(a[first], a[lastS1]);
  return lastS1;
}

static void quicksort(int a[], int first, int last) {
  if (first < last) {
    int pivotIndex = partition(a, first, last);
    quicksort(a, first, pivotIndex - 1);
    quicksort(a, pivotIndex + 1, last);
  }
}

static void quicksort(int a[], int aSize) {
  quicksort(a, 0, aSize - 1);
}
// END-ALGORITHM

int main() {
  srand(time(NULL));
  const int trials = 5;
  double totalTime = 0;
  for (int i = 0; i < trials; i++) 
  {
      const int aSize = 10000000;
      int a [aSize];
      makeScrambledArray(a, aSize);
      clock_t startTime = clock();
      quicksort(a, aSize);
      clock_t endTime = clock();
      double seconds = 
        static_cast<double>(endTime - startTime) * 1000000 / (CLOCKS_PER_SEC);
      totalTime += seconds;
    }

  printf("time =%lf\n\n" , totalTime/trials);
}

Thanks to everyone in advance

[Rashakil Fol]

Your function random is broken! This is an awesome bug. It's broken in two ways.

First, it's broken because rand() may return RAND_MAX. In such a case, your random function is clearly broken, because it will return the value ceiling.

So the quick fix is to divide by RAND_MAX + 1.0 .

Now, you have to be careful. Even then your code is broken! Try running this code.

#include <cmath>
#include <cstdlib>

#include <iostream>

int main()
{
  double f = static_cast<float>(RAND_MAX - 64) / (RAND_MAX + 1.0);
  double g = static_cast<float>(RAND_MAX - 63) / (RAND_MAX + 1.0);

  std::cout << "f < 1.0: " << (f < 1.0)
	    << "; g < 1.0: " << (g < 1.0)
	    << std::endl;
}

You'll notice that it outputs false for one of the values, and true for the other!

Why? Why, the datatype float doesn't have enough precision to represent the value RAND_MAX on most computers (on some computers, RAND_MAX is 32768, which is small enough so that it can). So when you convert RAND_MAX to a float, it rounds to the nearest acceptable float. You can see that if rand() returns the value RAND_MAX - 63 or greater, your function random() will treat it the same as if it had returned RAND_MAX. float can only exactly represent integers up to 16777216, which is 2 to the 24th power.

So your problem's probably that rand() is returning a value too large for a float to distinguish between it an RAND_MAX. So cast it to a double instead.

[VernonDozier]

I think it's not allocating that huge of an array because you aren't using the new command. When I ran it, it crashed the way you had it, but when I changed it to allocate memory with the new command, it ran.

If nothing else, you can catch the bad_alloc exception so you can find out for sure whether that is the problem.

http://www.cplusplus.com/reference/std/new/bad_alloc.html

[Rashakil Fol]

Hm yes, VernonDozier identified what was actually causing your problem. Fix your random function, too, though.

[code46]

Your function random is broken! This is an awesome bug. It's broken in two ways.

I understand how you explained it and I think I fixed it. My new code looks like this. I am just checking to see if this is right. Thanks.

static int random(int ceiling) {    
    return static_cast<double>(RAND_MAX - 63) / (RAND_MAX + 1.0);;
}

I think it's not allocating that huge of an array because you aren't using the new command. When I ran it, it crashed the way you had it, but when I changed it to allocate memory with the new command, it ran.

I really don't know how to implement the new command but when I did the program just kept running with what I changed and never finished, is there something I am doing wrong. All I changed is it in the main. I don't know if it has to do with the random I changed either.

int main() {
    srand(time(NULL));
    const int trials = 1;
    double totalTime = 0;
    for (int i = 0; i < trials; i++) 
    {
        const int aSize = 10000000;
        int * a;
        a = new int[aSize];
        makeScrambledArray(a, aSize);
        clock_t startTime = clock();
        quicksort(a, aSize);
        clock_t endTime = clock();
        double seconds = 
            static_cast<double>(endTime - startTime) * 1000000 / (CLOCKS_PER_SEC);
        totalTime += seconds;
    }

    printf("time =%lf\n\n" , totalTime/trials);
}

Thanks again for all the help and patience.

[Rashakil Fol]

What the fuck? Your random function isn't random any more.

[code46]

Sorry I am confused on using the random function.

static_cast<int>((static_cast<double>(rand()) / RAND_MAX) * ceiling);

I was going to change it to that but with that still give me the whole range of integer values?

[Rashakil Fol]

Well it seems you didn't read my reply, so never mind.

[code46]

OK. Thank you anyways for your help.

[VernonDozier]

I really don't know how to implement the new command but when I did the program just kept running with what I changed and never finished, is there something I am doing wrong. All I changed is it in the main. I don't know if it has to do with the random I changed either.

int main() {
	srand(time(NULL));
	const int trials = 1;
	double totalTime = 0;
	for (int i = 0; i < trials; i++) 
	{
		const int aSize = 10000000;
		int * a;
		a = new int[aSize];
		makeScrambledArray(a, aSize);
		clock_t startTime = clock();
		quicksort(a, aSize);
		clock_t endTime = clock();
		double seconds = 
			static_cast<double>(endTime - startTime) * 1000000 / (CLOCKS_PER_SEC);
		totalTime += seconds;

               // add delete statement to release memory? - Vernon
    }

	printf("time =%lf\n\n" , totalTime/trials);
}

Thanks again for all the help and patience.

You need to stick some debugging statements to find out what the program is doing. If you couldn't allocate the memory and you don't "catch" the bad_alloc error, I believe the program will abort, so if it is going on forever, the problem is elsewhere. Put in some debugging statements to find out what's happening. Change the size of the array. Maybe it's just slow.

It doesn't matter here since you have a for-loop that is only being executed once (hence not much of a "loop"), but when you allocate memory inside of a loop, then fail to deallocate it (see red above) when you are done with it, you are going to get a memory leak. Other than that, the memory allocation part looks OK, but consider allocating BEFORE the loop and catching the bad_alloc error, as is done in the example I posted.

[code46]

Thanks for that help I figured that it was not allocating the memory right and now it seems to work fine.

I am going to debug some more.

thank you.