Selection sort does not sort the unsorted portion once no swapping position is reached?

Question

I've been struggling with this bug for almost 2 days, but so far no success. If anyone could point out what is wrong with my code, I would appreciate it very much.

Using my own random numbers (100, 155, 145, 53, 88, 77, 65, 1, 15), I run my selection sort program to get the output (1, 15, 53, 65, 77, 88, 88, 145, 100). It is working up to a point where no swapping is required: 88 happens to be located at the 'no-swapping-required' position. Once it is reached, it looks like my code copies it into the next position, and does not sort the rest of the array (unsorted portion) any more. I cannot see why it is myself.

The selection sort portion of my program is shown below.

The output of this coding is (sorry for messy lines);

I also did the GDB analysis on this portion, it didn't give me any useful information. May be this is because I'm not used to using it. At this point, I'm totally at sea. I don't know what to do next. Could anyone throw me a light?

Answer 1

The reason why 100 is ignored is because you're comparing values[min] with values[j] only. And since j is initially set to i + 1 which is 1, values[0] is totally ignored.

The role of the nested loop should be to iterate through the rest of the elements in the array, picking up the minimum value, swapping it with values[i] in case this minimum values is less than values[i], but the fact that the nested loop iterates as long as j is less than n - 1 never lets j be n - 1.

I know you did that because j is initially set to i + 1, but don't you think that the outer loop is the one that's supposed to iterate as long as i is less than n - 1 instead? Think about it and try to figure out why?

And you probably shouldn't be swapping (if you're gonna swap) inside the nested loop because this doesn't guarantee values[min] holds the minimum value yet.

Lastly, you should probably check whether any swaps happened because if there are no swaps, this means that the array is already sorted and you shouldn't bother continuing iterating.

After you do your best fixing the problems up here, you may take a look at this pseudocode for selection sort if you'd like to

for (i = 0 to i < n - 1, increment i by 1)
{
    create a boolean named swapped and set it to false
    create an int named min and set it to i

    for (j = i + 1 to j < n, increment j by 1)
        if (values[j] < values[min])
            set min to j

    if (values[min] < values[i])
    {
        swap values[min] and values[i]
        set swapped to true
    }

    if not swapped
        break
}

Answer 2

Thank's to Kareem's hint, I could finally solve my problem with a little modification to the original. I use a loop (inner loop) to walk-through the array to find the minimum value, which is given to outer loop to do just swapping. And if the program finds a location where no-swapping is required, it adds 1 to min, and proceed to the next step as described below.

Output of the program using my own random numbers as inputs, shows the following result suggesting the problem has been fixed.

There were a lot of hassles to reach this point. I learned it is a good practice to save the working c code(with/without bugs) in softcopy, or at least in hardcopy from where you could restart. Otherwise, you would have to start it over from the very beginning. Also better keep tracking what you've done to the previous code. I learned it in a hard way.