Selection Sort - Index of Min/Max

Question

I was looking through the selection sort algorithm on cprogramming.com and I think I found an error in the implementation.

If you work through the algorithm, there's a variable called "index_of_min" which I believe should be "index_of_max" (since when I tested it, it was sorting largest to smallest).

Thinking that it was a typo or a minor mistake, I checked out some other websites like wikipedia and some lesser known websites like geekpedia. It seems like they are call it index of min.

When I ran it through the debugger, it really seemed to me that it's the max value's index. Am I making a mistake somewhere?

Edit: As Svante pointed out, only the cprogramming implentation is wrong. Wikipedia and Geekpidia are fine.

Answer 1

The wikipedia and geekpedia sites seem to be correct, the cprogramming.com implementation actually has a bug; this:

if (array[index_of_min] < array[y])
  { index_of_min = y; }

has the order reversed, it should be:

if (array[y] < array[index_of_min])
  { index_of_min = y; }

Another fix would be to call the variable index_of_max, but I would expect a sorting algorithm to sort smallest to largest, and if this expectation is shared by the majority of programmers (as I presume), the principle of least astonishment rather demands the above fix.

Answer 2

You are right. The code from that website (shown below) is incorrect.

for(int x = 0; x < n; x++)
    {
     int index_of_min = x;
     for(int y = x; y < n; y++)
     {
      if(array[index_of_min] < array[y])    /* Here's the problem */
      {
       index_of_min = y;
      }
     }
     int temp = array[x];
     array[x] = array[index_of_min];
     array[index_of_min] = temp;
    }

At the end of the inner loop, for(int y=x; y<n; y++), the variable, index_of_min, holds the index of the maximum value. Assuming it was designed to sort the array from largest to smallest, this is a poorly named variable.

If you want the array sorted smallest to largest (as one would expect), you need to reverse the if statement:

if (array[y] < array[index_of_min])
{
    index_of_min = y;
}

Enjoy,

Robert C. Cartaino

Answer 3

I've only just read the code, but it looks like you're right: either index_of_min is misnamed or the comparison is backwards.

It isn't as strange as it might seem to see this error in several places. It's quite likely that each is copied from a single common source.

Answer 4

From Cprogramming.com "It works by selecting the smallest (or largest, if you want to sort from big to small) element of the array and placing it at the head of the array" So they have it sorting from large to small, the code isent wrong, nor is the variable naming, index_of_min keeps track of the starting point int the array (0) and then moves forward in that array. ie index_of_min keeps the smallest index value. Do not get it confused with whatever the value is at that index.