helpers.c is not sorting my array and I'm running low on ideas on how to fix it

Question

My first question on this board and I really need some help in order to figure out what could be wrong with my code. I decided to go with a a selection sort but as soon as I run ./generate 2 2 in order to check if it works i get this unsorted list.

38906
31103

I implemented the code as follows:

for (int i = 0; i < n; i++)
{
    int min = i;

    for (int j = i+1; j < n; j++)
    {
       if (values[min]>values[j])
       {
            min = j;
             int temp = values[min];
             values [min] = values [i];
             values [i] = temp;
       }

    }

}


return ;

It would be great if somebody could point me in the right direction. Am I actually checking my code in the right way. I couldn't figure out how to use gdb for debugging since there is no ruining file just the helpers.c.

Thank you in advance!

Answer 1

The pseudocode for selection sort is as follows

for int i = 0 to i < n - 1, increment i by 1
{
    declare an int named min and set it to i

    for int j = i + 1 to j < n, increment j by 1
    {
        if values[min] > values[j]
        {
            set min to j
        }
    }

    swap values[i] and values[min]
}

You did most of it correctly though! However, you shouldn't be swapping the two values every time values[min] > values[j] because that would mess things up. Consider the following example

array: 5, 4, 3, 2, 1
pick the 5
walkthrough the list {4, 3, 2, 1} and pick the least element (i.e., 1)
swap it with the 5
array: 1, 4, 3, 2, 5
...

This way, you guarantee that after the first iteration of the outer loop, the least element in the array will be positioned at index 0.

What you're doing is something like

array: 5, 4, 3, 2, 1
set i to 0
set min to i
set j to 1
walkthrough the list {4, 3, 2, 1}
if values[min] > values[j]
{
    set min to j
    swap them
}

array: 4, 5, 3, 2, 1
i is still 0
min = 1
j is now 2
if (values[min] > values[j])
{
    set min to j
    swap them
}

array: 4, 3, 5, 2, 1
...

array: 4, 3, 2, 1, 5
then i = 1

and you'll never get back to values[0] (which is 4) again even though it's not in it's correct position yet.