# What is wrong with my sorting algorithm?

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

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)

• 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 :) 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. Oct 4 '16 at 16:40
• You're right, I meant to do that. But typed it wrong. Oct 4 '16 at 16:43
• And now it's fixed, thx so much Oct 4 '16 at 16:43
• That was indeed the problem. I removed that variable as soon as I saw I mistyped it. Oct 4 '16 at 17:49

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;

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