What is wrong with my sorting algorithm?

Question

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. ;)

Answer 1

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)

Answer 2

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;