0

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