2

I have been running gdb on this, and it's true, the values are not sorted. But my logic seems fine. This is the selection sort, anyone know what I am missing?

int min, hold, i, j;
    for (i = 1; i < (n - 1); i++)
    {
        min = i;
        for (j = i + 1; j < n; j++)
        {
            if (values[j] < values[min])
                min = j;
            if (min != i)
            {
                hold = values[j];
                values[j] = values[i];
                values[i] = hold;
            } 
        }
     } 

I got ideas for this code from the video Selection Sort:

7

The code has a few errors.

for (i = 1; i < (n - 1); i++)

The values array is zero based, whereas i starts at an index of 1, which is the second value in the array. If the largest number happened to be in the first position it will be skipped. i should start at zero.

{
    min = i;
    for (j = i + 1; j < n; j++)
    {

These lines are correct. min stores the index of the minimum item. j iterates over all the "unsorted" items.

        if (values[j] < values[min])
            min = j;

These lines are also correct. This checks if a value in the unsorted portion of the list is less than the value at the end of the sorted portion of the list.

        if (min != i)
        {
            hold = values[j];
            values[j] = values[i];
            values[i] = hold;
        } 

This is the second place where an error occurs, and there are two errors here. The first error is that it swaps the value in the unsorted portion at i, with the value at j. This should actually swap the value of i with the value of min. Think of i as the end of the sorted list. You want to take the smallest value you find in the unsorted list (indicated by j), and swap it with whatever is at the end of the sorted list.

That was the first problem with that block. The second problem is when the swap occurs. The swap occurs whenever the position of the min value does not match i, or whenever the position of the smallest value is not the last value in the list. This occurs on every iteration of the j loop, which is not necessary. The j loop only needs to locate the min value. The actual swap can happen after the j loop.

Finally, another potential problem exists, in that the code assumes the list is at least two elements in size. As far as I recall, check50 never tested with less than three values, so you may never actually encounter this error. However, for correctness, you may want to add a condition which only performs the sort if n is two or more.

Putting this all together, the code might look like this:

// behaviour is undefined if n < 2, will segfault, or return nonsense result
if (n < 2) 
{
    return;
}

int min, hold, i, j;

// loop through all but the last element in the array
// start at the first value, which is index 0
for (i = 0; i < (n - 1); i++)
{
    min = i;

    for (j = i + 1; j < n; j++)
    {
        // find and store the position of the smallest value
        // if there is no value smaller than the last value in the unsorted list, 
        // then min == i at the end of the loop
        if (values[j] < values[min])
        {
            min = j;
        } 
    }

    // swap the min value with the value at the end of the sorted list
    if (min != i) 
    {
        hold = values[i];
        values[i] = values[min];
        values[min] = hold;
    }
 } 

References:

| improve this answer | |
  • Thank you so much Luke, that was it! I don't know why it's so hard to visualize, it's like my brain can't hold the place of where the number is and the value it has, then compare with all the others, I forget the positions and values. You should seriously be a teacher! Your explanations are SO wonderfully thorough, even for strugglers like me. I guess I was thinking the 'j' position was the one to swap, since it got assigned the min, but you're right, I should use that min value, so other swaps don't happen, in case it never passes the 'min` test so to speak! I can't thank you enough. :) – Azurespot Aug 24 '14 at 1:30
  • You know what was weird though, Luke, is in the Selection Sort short, it uses i = 1 in that first loop. I didn't know why at the time (although I thought it was odd, maybe they just wanted to loop past the first one? But it still needed it's value checked) and they didn't explain why either, so it's odd they would show something wrong! – Azurespot Aug 24 '14 at 1:42
  • The videos are not wrong. I have linked both relevant videos I could find, and both show i being zero, although maybe the short could be misinterpreted. In Tommy's video, he points to the 23 as being the first value. Since arrays are zero based, the first value is actually values[0]. You may have heard them refer to a wall to separate the sorted portion from the unsorted portion. In your code j is the wall, which starts at the second value, or values[1]. – Luke Van In Aug 24 '14 at 12:35
  • 1
    Luke, I posted the screenshot of the video Selection Sort above in my original post, where they have i = 1. But good to know that j is considered to be a wall, thanks. – Azurespot Aug 24 '14 at 20:54
  • 1
    I totally missed that, well spotted - that looks like it's from Tommy's video. The code doesn't seem right, but I could be mistaken. It doesn't make sense how it would work if the first value is skipped. Unless there's something I'm missing. I would say it's a type. Zamyla's video has similar code, except it starts with i = 0. – Luke Van In Aug 24 '14 at 21:15

You must log in to answer this question.

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