New Topic/Question
Reply
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector> // provides Vector
#include <algorithm> // provides built-in sort
#include <sys/times.h> // provides tms timing struct
#include <assert.h>
#include "LList.cpp"
#include "Merge.cpp" // include your sorting LList class
using namespace std;
struct tms tmsstart, tmsend; // tms is declared in sys/times.h
// tmsstart & tmsend are structures to hold timing info
// Global settings
struct gA_t {
int alg; // -a algorithm
int min; // -m min n
int max; // -x max n
float scale; // -s scaling factor between steps
} gA;
/*
* Displays program usage
*/
void displayUsage(){
cout << "Usage: mySort [OPTION]...\n\n";
cout << "Time different sort algorithms with lists of various sizes.\n";
cout << " -a <int> Algorithm to use.\n";
cout << " -m <int> Starting list size\n";
cout << " -x <int> Ending list size\n";
cout << " -s <float> Scaling factor\n\n";
}
/*
* Prints the number of seconds elapsed between the stored times in tmsstart
* and tmsend;
*/
void printTime(){
long clktck = sysconf(_SC_CLK_TCK);
printf("%f",
(tmsend.tms_utime - tmsstart.tms_utime) / (double) clktck);
}
/**
* Main for program.
*/
int main(int argc, char* argv[]) {
gA.alg = 1; // Set defaults
gA.min = 20;
gA.max = 1000;
gA.scale = 2.0;
int val = gA.min;
int j;
int array[val];
//sets array
for(int i = 0; i <= val; i++){
array[i] = rand() % 200;
j=i;
}
//sorts array
MergeSort (begin, end, array ) ;
//the following prints the array
for (int i = 0; i <= end ;i++ ){
cout << array[i] << endl;
}
//assert(isSorted(??)); // good idea to make sure it's really sorted
// fill in rest of cases and sort algorithms here
// ...
// print size and execution time printTime();
return 0;
}
This is the Main program above. It calls the MergeSort function and it then references the following.
#include <iostream>
using namespace std;
void Merge(int begin, int end, int Array[], int mid) {
// make comparitives and create subarray
int* ArrayTemp = new int[end]; // creates a temp array
int beg =0 ; // takes sub array and has the placehold begining
int beg2= mid+1; // start of second subarray
int last = mid; // end of the first subarray
int last2 = end; // end of the second subarray
int index = beg;
//do the following as long as the array isn't empty or has one number
while( (beg <= last) && (beg2 <= last2 )){
if (Array[beg] <= Array[beg2]){ // if the subarray1 first is less than subarray2
ArrayTemp[index] = Array[beg] ; //temparray at index value will be subarray1
beg++; //increase the value of the arraysubset1 so next comp is beg[2] vs beg2[1]
}
//if the above is not true then put subarray2 value into the index of the temp array.
else{
ArrayTemp[index] = Array[beg2];
beg2++ ;
}
index ++;
}
//the following 2 while loops basically say if one of the subarrays is empty add the rest of
//the other array into the temp array.
while (beg <= last ) {
cout <<"while loop active" <<endl;
ArrayTemp[index] = Array[beg];
index++;
beg++;
}
while (beg2 <= last2 ) {
cout <<"while loop active 1" <<endl;
ArrayTemp[index] = Array[beg2];
index++;
beg2++;
}
//make index equal to the origin of the array
// make the array permanent. Place all values of the temp array into the actual array.
for (int i = 0; i <= end ;i++ ){
Array[i] = ArrayTemp[i];
}
delete [] ArrayTemp;
}
void MergeSort (int begin , int end, int Array[]) {
//check and see if the beginning of the array is less than the end of the array
//if so then find the middle and recursively call the function until it divies up everything.
if ( begin >= end) {
return; }
else {
int mid;
mid = (begin+end)/2 ;
MergeSort( begin, mid, Array); //recursive call keeps breaking down array
MergeSort(mid+1, end, Array); // recursive call keeps breaking down array.
Merge ( begin, end, Array, mid);
}
}
The issue is that the merge function sorts like 99.9 percent of the items passed but it keeps missing one or two. For example if the system passes the values 183 86 177 115 193 135 186 92 49 21 162 27 90 59 163 126 140 26 172 136 11 the output is not coming out the way it should. Instead the output is 26 27 49 59 86 90 91 126 135 136 140 162 163 172 177 183 115 186 21 193. Clearly 21 and 115 are not greater than 177 but I do not understand where the issue is. I have checked the while loops and thrown cout statements in every section of the code (taken out to make easy readability) but I am at a loss. Would anyone have ANY ideas whatsoever. This would be entirely helpful. Thanks so much !
MultiQuote
| 