Итак, проблема в том, что я сделал этот MergeSort, который работает для меньших массивов, но не для больших массивов в больших массивах, он вставляет дополнительный ноль в начале, как вы можете видеть ниже.
------------------------------------------------
SORTING TESTS: START
Problem: 323, 389, 881, 821, 663, 964, 958, 68, 988, 624, 44, 288, 226, 317, 347, 840, 241, 940, 8, 461, 125, 686, 917, 400, 378, 158, 171, 823, 804, 331, 930, 717, 189, 850, 790, 481, 983, 152, 575, 408, 888, 570, 872, 671, 734, 671, 850, 428, 36, 306, 700, 916, 868, 781, 463, 385, 820, 606, 727, 584, 563, 815, 717, 138, 759, 975, 177, 293, 762, 686, 498, 8, 992, 519, 212, 686, 608, 663, 656, 545, 618, 968, 710, 150, 534, 283, 506, 769, 794, 413, 495, 771, 210, 365, 125, 233, 272, 363, 692, 95,
Solution: 8, 8, 36, 44, 68, 95, 125, 125, 138, 150, 152, 158, 171, 177, 189, 210, 212, 226, 233, 241, 272, 283, 288, 293, 306, 317, 323, 331, 347, 363, 365, 378, 385, 389, 400, 408, 413, 428, 461, 463, 481, 495, 498, 506, 519, 534, 545, 563, 570, 575, 584, 606, 608, 618, 624, 656, 663, 663, 671, 671, 686, 686, 686, 692, 700, 710, 717, 717, 727, 734, 759, 762, 769, 771, 781, 790, 794, 804, 815, 820, 821, 823, 840, 850, 850, 868, 872, 881, 888, 916, 917, 930, 940, 958, 964, 968, 975, 983, 988, 992,
Sorted(Testing): 0, 8, 8, 36, 44, 68, 95, 125, 125, 138, 150, 152, 158, 171, 177, 189, 210, 212, 226, 233, 241, 272, 283, 288, 293, 306, 317, 323, 331, 347, 363, 365, 378, 385, 389, 400, 408, 413, 428, 461, 463, 481, 495, 498, 506, 519, 534, 545, 563, 570, 575, 584, 606, 608, 618, 624, 656, 663, 663, 671, 671, 686, 686, 686, 692, 700, 710, 717, 717, 727, 734, 759, 762, 769, 771, 781, 790, 794, 804, 815, 820, 821, 823, 840, 850, 850, 868, 872, 881, 888, 916, 917, 930, 940, 958, 964, 968, 975, 983, 988, 992,
Sorted(InsertionSort): 8, 8, 36, 44, 68, 95, 125, 125, 138, 150, 152, 158, 171, 177, 189, 210, 212, 226, 233, 241, 272, 283, 288, 293, 306, 317, 323, 331, 347, 363, 365, 378, 385, 389, 400, 408, 413, 428, 461, 463, 481, 495, 498, 506, 519, 534, 545, 563, 570, 575, 584, 606, 608, 618, 624, 656, 663, 663, 671, 671, 686, 686, 686, 692, 700, 710, 717, 717, 727, 734, 759, 762, 769, 771, 781, 790, 794, 804, 815, 820, 821, 823, 840, 850, 850, 868, 872, 881, 888, 916, 917, 930, 940, 958, 964, 968, 975, 983, 988, 992,
assertion "isArrEqual(sortThis, &solutionArr[1], solutionArr[0])" failed: file "
/cygdrive/c/src/universal-repos/datastructures-and-algorithms/main.c", line 119,
function: sortingTest
a
Process finished with exit code 0
Ниже вы можете увидеть тестирование и реализацию mergeSort
Я считаю, что ошибка заключается в функции слияния, но если бы я знал, что делал, то мне бы удалось исправить эту ошибку.
int *mergeSortShell(const int *const sortThis, int size) {
if(sortThis == NULL || size < 1){
return NULL;
}
int * copyArr = arrCopy(sortThis, 0, size);
mergeSort(copyArr, 0, size);
return copyArr;
}
void mergeSort(int * sort, int left, int right) {
//the array and left should be zero and right bound right you be the size of the array
if (sort == NULL) {
return;
}
if (right > left) {
int middle = (right - left);
if (middle % 2 != 0){
middle--;
}
middle = middle / 2 + left;
mergeSort(sort, left, middle);
mergeSort(sort, middle + 1, right);
merge(sort, left, middle, right);
}
}
void merge(int *mergeThis, int left, int middle, int right) {
if (mergeThis == NULL) {
return;
}
int leftSize = (middle - left) + 1;
int rightSize = right - middle;
int i, j, k; //iterators to be used throughout the function
int leftArray[leftSize + 1], rightArray[rightSize + 1];//tempArrays
leftArray[leftSize] = INT_MAX;
rightArray[rightSize] = INT_MAX;
for (i = 0; i < leftSize; i++) {
leftArray[i] = mergeThis[left + i];
}
for (i = 0; i < rightSize; i++) {
rightArray[i] = mergeThis[middle + 1 + i];
}
i = 0;//index of leftArray
j = 0;//index of rightArray
k = left;//index of sortCpy
while (i < leftSize && j < rightSize) {
if (leftArray[i] <= rightArray[j]) {
mergeThis[k] = leftArray[i];
i++;
} else {
mergeThis[k] = rightArray[j];
j++;
}
k++;
}
//if any of the the right or left has remaining elements
//this will run
while (i < leftSize) {
mergeThis[k] = leftArray[i];
k++;
i++;
}
while (j < rightSize) {
mergeThis[k] = rightArray[j];
k++;
j++;
}
}
int *arrCopy(const int *const arrayPtr, int leftBound, int size) {//leftbound should be left at zero if you want it
// to copy the whole array
int *sortCpy = NULL;
sortCpy = (int *) malloc(sizeof(int) * (size - leftBound));
if (arrayPtr == NULL) {
return NULL;
}
for (int i = 0, j = leftBound; i < (size - leftBound) && j < size; i++, j++) {
sortCpy[i] = arrayPtr[j];
}
//memcpy(sortCpy, arrayPtr, size * sizeof(int));
if (isArrEqual(sortCpy, arrayPtr, size) == false) {
return NULL;
}
return sortCpy;
}
bool sortingTest() {
printf("------------------------------------------------\n");
printf("SORTING TESTS: START\n");
const int l1[] = {3, 1, 5, 10, 8, 7};
const int l1solution[] = {1, 3, 5, 7, 8, 10};
const int l2[] = {5, 2, 9, 6, 1, 2};
const int l2solution[] = {1, 2, 2, 5, 6, 9};
const int pNum[] = {1, 9, 9, 5, 0, 1, 2, 6, 0, 0, 9, 6};
const int pNumSolution[] = {0, 0, 0, 1, 1, 2, 5, 6, 6, 9, 9, 9};
assert(isArrEqual(l1, l1, 6) == true);
assert(isArrEqual(l1, l1solution, 6) == false);
assert(isArrEqual(l2, l2solution, 6) == false);
assert(isArrEqual(NULL, NULL, 5) == false);
assert(arrPrint(NULL, INT_MIN) == false);
// assert(isArrEqual(pNum, pNumSolved, 12));
assert(load_file(NULL) == NULL);
char sortingProblem[] = {"../sorting_problems/test-10-1-problem"};
char sortingSolution[] = {"../sorting_problems/test-10-1-solution"};
const int * const problemArr = load_file(sortingProblem);
const int * const solutionArr = load_file(sortingSolution);
assert(problemArr != NULL);
assert(solutionArr != NULL);
int *copyTest = NULL;
copyTest = arrCopy(&solutionArr[1], 0, solutionArr[0]);
assert(isArrEqual(copyTest, &solutionArr[1], solutionArr[0]));
free(copyTest);
copyTest = arrCopy(&problemArr[1], 0, problemArr[0]);
assert(isArrEqual(copyTest, &problemArr[1], problemArr[0]));
free(copyTest);
int *sortThis = NULL;
int *reference = NULL;
//----------------MERGE SORT START----------------------
assert(mergeSortShell(NULL, INT_MIN) == NULL);
assert(mergeSortShell(l1, INT_MIN) == NULL);
sortThis = mergeSortShell(l1, (sizeof(l1) / sizeof(int)));
assert(sortThis != NULL);
assert(isArrEqual(sortThis, l1solution, sizeof(l1) / sizeof(int)));
free(sortThis);
sortThis = mergeSortShell(l2, (sizeof(l2) / sizeof(int)));
assert(sortThis != NULL);
assert(isArrEqual(sortThis, l2solution, sizeof(l2) / sizeof(int)));
free(sortThis);
sortThis = mergeSortShell(pNum, (sizeof(pNum) / sizeof(int)));
assert(sortThis != NULL);
assert(isArrEqual(sortThis, pNumSolution, sizeof(pNum) / sizeof(int)));
free(sortThis);
sortThis = mergeSortShell(&problemArr[1], problemArr[0]);
assert(sortThis != NULL);
//region Status
printf("Problem: \t\t\t\t");
arrPrint(&problemArr[1], problemArr[0]);
printf("Solution:\t\t\t\t");
arrPrint(&solutionArr[1], solutionArr[0]);
printf("Sorted(Testing):\t\t");
arrPrint(sortThis, solutionArr[0]+1);
//endregion
assert(isArrEqual(sortThis, &solutionArr[1], solutionArr[0]));
free(sortThis);
/**/
// ----------------MERGE SORT END------------------------
//----------------QUICK SORT START----------------------
//Might not implement
//----------------QUICK SORT END------------------------
free((int*)problemArr);
free((int*)solutionArr);
printf("SORTING TESTS: END\n");
printf("------------------------------------------------\n");
return 0;
}
int main() {
printf("------------------------START OF TESTS------------------------\n");
altLinkedListTest();
arrayTest();
sortingTest();
printf("------------------------END OF TESTS--------------------------");
return 0;
}