0

I implemented the helpers for sort and search. Using basic implementations of quicksort and binarysearch. When I ran check50 cs50/2017/x/find/less there was a weird error for the sorting part:

:) helpers.c compiles.
:( sorts {5,4,3,2,1}
    expected "3", not "\n5\n"
:( sorts {5,3,1,2,4,6}
    expected "5", not "\n6\n"
:) finds 28 in {28,29,30}

All my own tests work just fine and when I tried manually sort the same array and printing the output to the command line, it does sort [5,4,3,2,1] to [1,2,3,4,5].

I don't know which part of the helpers file would be most useful for you to so I just gonna post the whole thing here:

/**
* helpers.c
*
* Helper functions for Problem Set 3.
*/

#include <cs50.h>

#include "helpers.h"

int binarySearch(int values[], int left, int right, int value)
{
    if (right >= left)
    {
        // get the middle position in the array
        int mid = left + ( right - left ) / 2;

        // if the middle is the result, return it
        if (values[mid] == value)
        {
            return mid;
        }

        // if the middle value is bigger than the search value, the result can
        // only be in the part below the middle value
        if (values[mid] > value)
        {
            return binarySearch(values, left, mid - 1, value);
        }

        // else the value has to be in the part above the middle value
        return binarySearch(values, mid + 1, right, value);
    }

    // when the element is not found
    return -1;
}

int divide(int left, int right, int values[])
{
    int i = left;
    int j = right - 1;
    int pivot = values[right];
    do {
        while (values[i] < pivot && i < right - 1) {
            i += 1;
        }
        while (values[j] >= pivot && j > left) {
            j -= 1;
        }
        if (i < j) {
            int temp = values[i];
            values[i] = values[j];
            values[j] = temp;
        }
    } while (i < j);

    if (values[i] > pivot)
    {
        int temp = values[i];
        values[i] = values[right];
        values[right] = temp;
    }
    return i;
}

void quicksort(int left, int right, int values[])
{
    if (left < right)
    {
        int divider = divide(left, right, values);
        quicksort(left, divider - 1, values);
        quicksort(divider + 1, right, values);
    }
    return;
}


/**
* Returns true if value is in array of n values, else false.
*/
bool search(int value, int values[], int n)
{
    int foundIndex = binarySearch(values, 0, n, value);
    return foundIndex != -1;
}

/**
* Sorts array of n values.
*/
void sort(int values[], int n)
{
    if (n >= 2) {
        quicksort(0, n - 1, values);
    }
    return;
}
0

Not a weird error. Simply put, the sort function isn't working correctly. Try adding a loop to print out the list at the end of the sort function to verify that the list is sorted. It'll help you check the list while you debug. You can also test it using the same data that check50 uses in the two sort tests as well as your own random data.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

1
  • Well, I actually did what you said already. I added a loop to print the list values before and after the call to sort. There it worked just fine. I ended up using a different sorting algorithm. Bubble-sort instead of quick-sort.
    – Chris
    Dec 23 '17 at 15:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .