I'd appreciate any help or advice you guys are willing to offer.
I wrote a program for my intro to programming class that counts comparisons for a bubble sort and a selection sort algorithm. Here's the assignment description:
Modify bubble sort (for integers) so that it counts the the number of comparisons and returns it as the value of the function. Do the same with selection sort.
Write a main method that declares two arrays of 100 ints, generates 100 random integers (you don't need to limit the range), storing each random number in both arrays, so that you end up with two identical arrays. Pass one of them to the modified bubble sort and print out the return value, then pass the other array to the modified selection sort and print out the return value (label your outputs of course - the specifics of the output format are up to you as long as they are clear). Repeat this with array sizes of 1,000, 10,000 and 100,000.
My program works perfectly in Xcode, but I receive a segmentation fault when compiling in g++. My school's server runs a pre-c++0x version of the compiler and my computer's more modern version of g++ fails out as well.
Here's the error:
Segmentation fault: 11
I tried stepping through this in gdb, but I'm VERY new to this and I wasn't sure how to skip past these long loops while filling arrays.
I think vectors would be possibly easier to debug (given my research on SO regarding this problem), alas, the professor is requiring us to use arrays.
Caution: This program is fairly processor intensive if you feel like running it.
Here's the code:
#include <iostream> /* cout */
#include <ctime> /* time for seeding RNG */
#include <cstdlib> /* srand() */
void randomFill(int array[], int size); //fills an array with random numbers
void copyArray(int selectionArray[], int bubbleArray[], int size); //copies from selection to bubble arrays
//ascending sorts
int bubbleSort(int IntsBubble[], int size);
int selectionSort(int IntsSelection[], int size);
int main() {
srand(static_cast<int>(time(NULL))); //seed random number generator
/* 'Twin' arrays declared, filled with random numbers and sorted */
/* 100 Integers */
int hundredIntsSelection[100];
randomFill(hundredIntsSelection, 100);
int hundredSelectionComparisons = selectionSort(hundredIntsSelection, 100);
int hundredIntsBubble[100];
copyArray(hundredIntsSelection, hundredIntsBubble, 100);
int hundredBubbleComparisons = bubbleSort(hundredIntsBubble, 100);
/* 1000 Integers */
int thousandIntsSelection[1000];
randomFill(thousandIntsSelection, 1000);
int thousandSelectionComparisons = selectionSort(thousandIntsSelection, 1000);
int thousandIntsBubble[1000];
copyArray(thousandIntsSelection, thousandIntsBubble, 1000);
int thousandBubbleComparisons = bubbleSort(thousandIntsBubble, 1000);
/* 10,000 Integers */
int tenThousandIntsSelection[10000];
randomFill(tenThousandIntsSelection, 10000);
int tenThousandSelectionComparisons = selectionSort(thousandIntsSelection, 10000);
int tenThousandIntsBubble[10000];
copyArray(tenThousandIntsSelection, tenThousandIntsBubble, 10000);
int tenThousandBubbleComparisons = bubbleSort(tenThousandIntsSelection, 10000);
/* 100,000 Integers */
int hundredThousandIntsSelection[100000];
randomFill(hundredThousandIntsSelection, 100000);
int hundredThousandSelectionComparisons = selectionSort(hundredIntsSelection, 100000);
int hundredThousandIntsBubble[100000];
for (int counter = 0; counter < 100000; counter++) { /* The program encounters runtime errors if I pass an array this large to copyArray */
hundredThousandIntsBubble[counter] = hundredThousandIntsSelection[counter];
}
int hundredThousandBubbleComparisons = bubbleSort(hundredThousandIntsBubble, 100000);
/* Here we're outputting our results to the user */
std::cout << "This program sorts twin arrays of 100, 1,000, 10,000 and 100,000 random integers and records the number of comparisons, displayed below.";
std::cout << std::endl;
std::cout << std::endl << "Results of random selection sort (100 integers): " << hundredSelectionComparisons << " comparisons.";
std::cout << std::endl << "Versus bubble sort of the same: " << hundredBubbleComparisons << " comparisons.";
std::cout << std::endl;
std::cout << std::endl << "Results of random selection sort (1,000 integers): " << thousandSelectionComparisons << " comparisons.";
std::cout << std::endl << "Versus bubble sort of the same: " << thousandBubbleComparisons << " comparisons.";
std::cout << std::endl;
std::cout << std::endl << "Results of random selection sort (10,000 integers): " << tenThousandSelectionComparisons << " comparisons.";
std::cout << std::endl << "Versus bubble sort of the same: " << tenThousandBubbleComparisons << " comparisons.";
std::cout << std::endl;
std::cout << std::endl << "Results of random selection sort (100,000 integers): " << hundredThousandSelectionComparisons << " comparisons.";
std::cout << std::endl << "Versus bubble sort of the same: " << hundredThousandBubbleComparisons << " comparisons.";
std::cout << std::endl << std::endl;
/* Bubble sort makes far more swaps than Selection sort, even though they make the same number of comparisons. */
return 0;
}
//fills arrays with random ints for sorting
void randomFill(int array[], int size) {
for (int counter = 0; counter < size; counter++) {
array[counter] = rand();
}
}
void copyArray(int selectionArray[], int bubbleArray[], int size) {
for (int counter = 0; counter < size; counter++) {
bubbleArray[counter] = selectionArray[counter];
}
}
int bubbleSort(int IntsBubble[], int size) {
int temp;
int counter;
bool swap;
do {
swap = false;
for (counter = 0; counter < size; counter++) {
if (IntsBubble[counter] > IntsBubble[counter + 1]) {
temp = IntsBubble[counter];
IntsBubble[counter] = IntsBubble[counter + 1];
IntsBubble[counter + 1] = temp;
swap = true;
}
}
} while (swap);
return counter;
}
int selectionSort(int IntsSelection[], int size) {
int startScan, minIndex, minValue, index = 0;
for (startScan = 0; startScan < (size - 1); startScan++) {
minIndex = startScan;
minValue = IntsSelection[startScan];
for (index = startScan + 1; index < size; index++) {
if (IntsSelection[index] < minValue) {
minValue = IntsSelection[index];
minIndex = index;
}
}
}
return index;
}
If there's anything I can add to make helping me easier, please let me know. I would also appreciate any general debugging suggestions or resources. We haven't covered it at all so far in this course. Thanks!
Edit: Letting it run through gdb gets this error. I'm going to keep searching, but a quick web search didn't turn up anything useful:
warning: Could not open OSO archive file "/BinaryCache/corecrypto/corecrypto-233.1.2~26/Symbols/BuiltProducts/libcorecrypto_static.a"
warning: `/BinaryCache/coreTLS/coreTLS-35.1.2~2/Objects/coretls.build/coretls.build/Objects-normal/x86_64/system_coretls_vers.o': can't open to read symbols: No such file or directory.
warning: Could not open OSO archive file "/BinaryCache/coreTLS/coreTLS-35.1.2~2/Symbols/BuiltProducts/libcoretls_ciphersuites.a"
warning: Could not open OSO archive file "/BinaryCache/coreTLS/coreTLS-35.1.2~2/Symbols/BuiltProducts/libcoretls_handshake.a"
warning: Could not open OSO archive file "/BinaryCache/coreTLS/coreTLS-35.1.2~2/Symbols/BuiltProducts/libcoretls_record.a"
warning: Could not open OSO archive file "/BinaryCache/coreTLS/coreTLS-35.1.2~2/Symbols/BuiltProducts/libcoretls_stream_parser.a"
What does TLS even have to do with C++? Running it on the school machine says that it's missing debuginfos but I'd have to be root to install that.
Edit2: I followed this suggestion of making pointers for my larger arrays and deallocated them manually. This doesn't appear to have changed anything.
