pset3: sort -- Selection Sort Implementation

Question

I have been working away at my implementation of Insertion Sort for this problem set, and I've run into a predicament. I have gotten the sort function almost functional, however I'm sure we all know where almost really counts...

Currently, the sort function sorts everything correctly except a few indexes, which seems odd. You'll see what I mean after looking at my broken code and my sample output.

Any help is much appreciated. I feel I'm very, very close to the end of this one so I'm hoping someone might trigger an epiphany and I'll be able to solve it.

The code:

/**
  * Sorts array of n values.
  */
void sort(int values[], int n)
{
    for(int i = 0; i < n; i++) // debugging loop, prints array pre sort
{
    printf("%i, ", values[i]);
}

printf("\n");

int min = 0; // sets minimum to zero initially.
for(int i = 0; i < n - 1; i++) // first loop that starts on the 0th index of the values array
{
    for(int j = i + 1; j < n; j++) // loop that starts checking every value after the 0th index
    {
            if(values[j] < values[i] && values[j] < values[min]) // if current index (i) is less than current value (j), and is 
            {                                                    // less than current minimum, set minimum to value (j)
                min = j;                                          
                printf("DEBUG %i: %i\n", i, min);
            }
    }
    int temp = values[i]; // following lines are for swapping the variables around
    values[i] = values[min];
    values[min] = temp;
}
for(int i = 0; i < n; i++) // debugging loop, prints array post sort
{
    printf("%i, ", values[i]);
}
printf("\n");

return;

}

The sample output:

~/workspace/pset3/find/ $ make find
clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm
~/workspace/pset3/find/ $ ./generate 10 5 | ./find 11086

haystack[0] = 
haystack[1] = 
haystack[2] = 
haystack[3] = 
haystack[4] = 
haystack[5] = 
haystack[6] = 
haystack[7] = 
haystack[8] = 
haystack[9] = 
haystack[10] = 
34395, 17881, 51681, 12980, 33962, 56730, 11086, 31267, 16834, 55770, 
DEBUG 0: 1
DEBUG 0: 3
DEBUG 0: 6
DEBUG 1: 3
DEBUG 2: 8
DEBUG 5: 7
DEBUG 6: 8
DEBUG 8: 9
11086, 12980, 16834, 51681, 17881, 31267, 33962, 34395, 55770, 56730, 

Found needle in haystack!

~/workspace/pset3/find/ $ 

One thing I did notice in the sample output is that the DEBUG line isn't printing the value of i for some of the iterations, however that could just mean some of the numbers were swapped into their correct places.

As a side note, I did look through the other similar questions, however none of them appeared detailed enough to aid me, and some just did not pertain to my question.

Again, any help is appreciated!

Answer 1

Looks like some kind of select sort. For that to work, in the outer loop, before the inner loop, set min to i ("smallest non-sorted element so far is at index i"), and in the inner loop (starting at i+1 as it should), compare only elements at j and min, not i. As min is initialized to i each iteration of the outer loop, you don't have to handle it in any special way.