Counting sort in C apparently works but binarysearch doesn't

I am looking for help regarding the implementation of a counting sort function in the CS50 Course in week 3.

An int Array has to be sorted. I tested various unsorted arrays and my counting sort function seems to sort the array just correctly, yet my search functions won't work on the sorted array after. Could someone give me a hint?

void countsort( int array[], int size) {

    int count=0;
    int zahl=0;
    int max=65536;
    int countarr [max];
    int finalarr [size];

    memset (countarr, 0, sizeof(countarr));

    for(int i=0;i<size;i++) {
        zahl=array[i];
        countarr[zahl]++;
    }

    for(int i=0;i<max;i++) {

        while(countarr[i]>0) {
            finalarr[count]=i;
            countarr[i]--;
            count++;

        }
    }
    array=finalarr;

    for(int i=0;i<size;i++){
        printf(" %i ",array[i]);
    }
}

This is my search algorithm used after the array is sorted, it works with sort algorithms from other people.

bool binarysearch(int value, int values[], int n){

    int start=0,
        end=n,
        mid=0,
        midpos=0;

    while(end>0) {

        midpos=(start+end)/2; 

        mid=values[midpos];

        if(mid==value) return true;

        if(mid<value) start=++midpos;

        if(mid>value) end=--midpos;

    }
    return false;
} 

1 answer

  • answered 2017-06-17 18:52 Gassa

    1. In binarysearch, the loop condition while(end>0) is wrong. If we search for a value which is greater than at least one of the elements of the array, end will never be zero. Try changing it to while(end>=start), which literally means that the considered interval is non-empty.

    2. In countsort, the line array=finalarr; does not copy the whole array. Instead, the local variable array becomes a pointer to finalarr. The contents of the original array remain unchanged, and the sorted array is gone when you exit the function. This explains why your binary search works (better) with other sort functions.
      Try changing finalarr[count]=i; to array[count]=i; and get rid of finalarr completely, putting the values into array right away. Alternatively, you can use memmove instead of that line.