0

I don't know why my code didn't pass the check50 test.

It worked just fine for ./generate 1000 50 | ./find 127 and ./generate 1000 50 | ./find 128

Here's the result of check 50 and my code.

Any help would be greatly appreciated! :D

~/workspace/pset3/find/ $ check50 2016.find.more helpers.c :) helpers.c exists :) helpers.c compiles :) finds 42 in {42,43,44} :) finds 42 in {41,42,43} :( finds 42 in {40,41,42} \ expected an exit code of 0, not 1 :) finds 42 in {41,42,43,44} :) finds 42 in {40,41,42,43} :( finds 42 in {39,40,41,42} \ expected an exit code of 0, not 1 :) doesn't find 42 in {39,40,41} :) doesn't find 42 in {39,40,41,43} :( finds 42 in {42,40,39,41} \ expected an exit code of 0, not 1 https://sandbox.cs50.net/checks/68933a55bad0441986377cada4f7c308

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

#include <cs50.h>
#include<stdio.h>

#include "helpers.h"
void quick_sort(int arr[],int,int);

/**
 * Returns true if value is in array of n values, else false.
 */
bool search(int value, int values[], int n)
{
    //printf("entered search\n");
    if(n<=0) return false;

    // TODO: implement a searching algorithm
    int middle, first=0, last=n-1;
    middle=(first+last)/2;

    while (first <= last) {
      if (values[middle] < value)
         {
             first = middle + 1;    
             //printf("first=%d\n",first);
         }
      else if (values[middle] == value) {
         return true;
      }
      else
         {last = middle - 1;
             //printf("last=%d\n",last);
         }

      middle = (first + last)/2;
      //printf("middle=%d\n",middle);
   }

    return false;
}

/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    // TODO: implement an O(n^2) sorting algorithm
    quick_sort(values, 0 , n);
    return;
}

void quick_sort(int arr[],int low,int high)
{
    int pivot,j,temp,i;
    if(low<high)
 {
    pivot = low;
    i = low;
    j = high;

    while(i<j)
    {
        while((arr[i]<=arr[pivot])&&(i<high))
            {
                i++;
            }

        while(arr[j]>arr[pivot])
            {
                j--;
            }

     if(i<j)
        { 
            temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
    }

  temp=arr[pivot];
  arr[pivot]=arr[j];
  arr[j]=temp;

  quick_sort(arr,low,j-1);
  quick_sort(arr,j+1,high);

 }

}
2

This is a good lesson in why thorough testing is important. You have run a couple of tests above to check basic functionality (which is good), but since there wasn't thorough testing of special or corner cases, something got through.

Take a careful look at the check50 results. Did you notice that the only tests that failed are the ones where the target value, the needle, is the largest value in the list?

For programs like this, it's important to test special cases like the target being the largest or the smallest value in the list, a middle value, and to test for targets not in the list, but somewhere in the middle of the list, larger that all values, and smaller than all values.

I won't offer the fix here, but I'll make a suggestion. In the sort() function, print out the sorted list just before the return statement. Run the program with 40, 41 and 42 as the list. It will become instantly obvious what the problem is! Then, you can work on the solution. ;-)

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

1
  • Thank you very much! The problem is really in the sort() function.
    – Bank.NT
    Jun 9 '17 at 0:34

You must log in to answer this question.

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