0

I'm stuck. My program seems to run just fine, but when I run the CS50 check I don't get full results. I think there's something wrong with my sorting algorithm.

This is my feedback if I run this line (starts at 79):

for (int i = 0; i < (n); i++)
    {
        // int smallest is set to 65536, equal to const int MAX in find.c
        smallval = 65536;

        // find the smallest value
         for (int j = i; j < (n); j++)
         {
             if (values [j] < values [smallell])
             {
                 smallell = j;
             }

:) 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}

This is the feedback for my current code, which I stated below.

:) helpers.c exists :) helpers.c compiles :) finds 42 in {42,43,44} :( finds 42 in {41,42,43} \ expected an exit code of 0, not 1 :) finds 42 in {40,41,42} :) finds 42 in {41,42,43,44} :( finds 42 in {40,41,42,43} \ expected an exit code of 0, not 1 :) finds 42 in {39,40,41,42} :) doesn't find 42 in {39,40,41} :) doesn't find 42 in {39,40,41,43}

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

#include "helpers.h"

/**
 * Returns true if value is in array of n values, else false.
 */
void sort(int values[], int n);
int n;

bool search(int value, int values[], int n)
// Needle, haystack, size
{
   // Checks if the user entered a positive int, as amount of hay
   if (n < 1)
   {
       printf("We need a positive amount of hay, you stupid ;)\n");
       return false;
   }

   else
   {
        //  Binairy search

        int min = 0;
        int max = (n);

        while (min <= max)
        {
            int middle = ((max + min) / 2);
            printf("middle= %i", middle);

            if (value == values[middle])
            {
                return true;
            }

            else if (value < values[middle])
            {
                max = (middle - 1);
            }

            else
            {
                min = (middle + 1);
            }

        }
        return false;

   }

}

/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    // TODO: implement an O(n^2) sorting algorithm : Selection Sort


    int placeholder;
    int smallell;
    int smallval;



    for (int i = 0; i < (n-1); i++)
    {
        // int smallest is set to 65536, equal to const int MAX in find.c
        smallval = 65536;

        // find the smallest value
         for (int j = i; j < (n-1); j++)
         {
             if (values [j] < values [smallell])
             {
                 smallell = j;
             }
         }

        // Swap values of i and smallell
        placeholder = values [i];
        values [i] = values [smallell];
        values [smallell] = placeholder;
    }
    return;

}

Can anyone explain what is going wrong? Also some tips for testing my code would be really helpful. I don't know how to find this error myself and I don't want to rely on the cs50 check. ;)

0

Other than that, there are two other problems.

First, you're stopping your loops one element shorter than what you should be doing. You're using i < n - 1 and j < n -1 when you should be using either j < n or j <= n - 1. This is the first fix.

The second fix is that you're not updating smallell after each iteration of one of your loops, so elements end up being compared twice.

To fix this, you should do something like this after your first loop:

    for (int i = 0; i < n; i++)
    {
        // consider this the first unsorted
        smallell = i;

        // find the smallest value

         for (int j = i; j < n; j++)
         {
             if (values [j] < values [smallell])
             {
                 smallell = j;
             }
         }

So with this you fix your sorting algorithm. After you fix the sorting, try the search again (I haven't analyzed your search function, only the sorting algorithm)

5
  • I appreciate your feedback a lot, but I do not agree with your answer. I do reset smallell after each iteration. I set smallell to the highest possible value, so on the first iteration the value is always set to the value of the first element. I think your method is more logical, but it does not fix my problem. Also I don't think I have to search to n. n is the total amount of stacks generate and in the loop I search an array, which starts at 0. Therefore I can stop 1 iteration short of n. But correct my if may logic is not correct. And again I appreciate this discussion :) – Joeri Venekamp Oct 4 '16 at 16:37
  • You're not setting smallell to highest possible value, you're setting smallval, which is another variable! (and I don't really see why you're using this smallval variable and never comparing it to anything later). And an array starts at 0 and ends at n-1, you take care of that using J < n (that is, j is first integer less that n, which is n-1). If you use j < n - 1, you're stopping j at n - 2 (that is, first integer less than n -1). And with this you don't check the last element. – Yuri Laguardia Oct 4 '16 at 16:40
  • You're right, I meant to do that. But typed it wrong. – Joeri Venekamp Oct 4 '16 at 16:43
  • And now it's fixed, thx so much – Joeri Venekamp Oct 4 '16 at 16:43
  • That was indeed the problem. I removed that variable as soon as I saw I mistyped it. – Joeri Venekamp Oct 4 '16 at 17:49
1

Aren't you using smallell here without initializing it first?

if (values [j] < values [smallell])

I only saw you declaring smallel here, but you never assigned a value to it:

int smallell;

1
  • You're right. Unfortunately it didn't change the results of my program. – Joeri Venekamp Oct 4 '16 at 15:23

You must log in to answer this question.

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