i can't understand the problem in my code, can anyone explain to me where the problem in my code please. the book where i got my algorithm: Introduction to Algorithms, Third Edition i understand how the algorithm work but in coding it, its sort only the 4 first number and keep the other without sorting.

code:

`

#include <stdio.h>
void sortArr(int *nums,int arrSize){
// nums[start...end]
// nums[start...mid]  n1
// nums[mid 1...end]  n2
    int start, mid, end;
    start = 0;
    end = arrSize-1;
    mid = (end start)/2;
    int n1, n2;
    n1 = mid-start 1;
    n2 = end - mid;
    int l[n1], r[n2];
    for(int i=0;i<n1;i  ){
        l[i] = nums[start i];
    }
    for(int i=0;i<n2;i  ){
        r[i] = nums[mid 1 i];
    }
    int i, j;
    i =0;
    j = 0;
    for(int k=start;k<arrSize;k  ){
        if(l[i]<=r[j]){
            nums[k] = l[i];
            i  ;
        }else{
            nums[k] = r[j];
            j  ;
        }
    }
}
int main(){
    int arr[] = {3, 41, 52, 26, 38, 57, 9, 49};
    int arrsize = sizeof(arr)/sizeof(arr[0]);
    printf("before sorting: \n");
    for(int i=0;i<arrsize;i  ){
        printf("%d ", arr[i]);
    }
    sortArr(arr, arrsize);
    printf("\n after sorting: \n");
    for(int i=0;i<arrsize;i  ){
        printf("%d ", arr[i]);
    }
    return 0;
}

`

CodePudding user response：

Add this print command to the final loop: printf("%d %d %d\n", k, i, j);

n1 = n2 = 4, so both arrays have values only up to index 3. Yet in the final loop, you run i from 0 to 6. This cannot work.

You can add more print commands, run the algorithm with pen and paper, and hopefully find the place where it went wrong.

CodePudding user response：

There's quite a few problems with your code, including the fact that you've only implemented MERGE from the book (a subroutine for MERGESORT), and the book uses a trick of appending infinity to the "halves" of the array to avoid having code that handles when one of the halves is used up when merging.

Here's a working version based on the book algorithms. Compared to the code in the question, it also avoids the VLAs (variable length arrays) which are likely to fail on large input arrays, and uses the more correct size_t for array indexes.

The code adds some extra tests in the if statement for li and ri when merging which is a different way than the book's infinity trick, and works better in C.

The functions return 1 if successful, and 0 if unsuccessful (which can happen if you give end less than start or malloc fails). Assertions are used to check assumptions about the various indexes and sizes -- these should fail only if there's a bug in the code and can be compiled out.

It runs on a random array of a configurable size (currently 12345), and prints out ok or failed at the end depending whether the array is actually sorted. (Note: rand is normally to be avoided because it's usually a poor supply of random numbers, but it's fine here).

Note this code is carefully written, but it's still not very well tested so you may find bugs!

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int MERGE(int *nums, size_t start, size_t mid, size_t end) {
    size_t n1 = mid - start   1;
    size_t n2 = end - mid;
    assert(n1 > 0);
    assert(n2 > 0);
    int *L = malloc(n1 * sizeof(int));
    if (!L) return 0;
    int *R = malloc(n2 * sizeof(int));
    if (!R) {
        free(L);
        return 0;
    }
    for (size_t i = 0; i < n1; i  ) {
        assert(start   i <= mid);
        L[i] = nums[start   i];
    }
    for (size_t i = 0; i < n2; i  ) {
        assert(mid   1   i <= end);
        R[i] = nums[mid   1   i];
    }
    size_t li = 0, ri = 0;
    for (size_t i = 0; i <= end - start; i   ){
        if (li < n1 && (ri == n2 || L[li] <= R[ri])) {
            assert(li < n1);
            nums[start   i] = L[li  ];
        } else {
            assert(ri < n2);
            nums[start   i] = R[ri  ];
        }
    }
    free(R);
    free(L);
    return 1;
}

int MERGESORT(int *nums, size_t start, size_t end) {
    if (end < start) return 0;
    if (end == start) return 1;
    size_t mid = start   (end - start) / 2;
    if (!MERGESORT(nums, start, mid)) return 0;
    if (!MERGESORT(nums, mid 1, end)) return 0;
    return MERGE(nums, start, mid, end);
}

#define N 12345
int main(){
    int arr[N];
    for (size_t i = 0; i < N; i  ) {
        arr[i] = rand();
    }
    size_t arrsize = sizeof(arr)/sizeof(arr[0]);
    printf("before sorting: \n");
    for(size_t i=0; i<arrsize; i  ){
        printf("%d ", arr[i]);
    }
    printf("\n");
    if (!MERGESORT(arr, 0, arrsize-1)) {
        printf("failed\n");
        exit(1);
    }
    printf("after sorting: \n");
    int failed = 0;
    for(size_t i=0; i<arrsize; i  ){
        if (i > 0 && arr[i] < arr[i-1]) failed = 1;
        printf("%d ", arr[i]);
    }
    printf("\n");
    printf("%s\n", failed ? "failed" : "ok");
    return 0;
}