question related to : selection sort in C-CodePudding

Selection sort in C usually written in the form of the following code below, introducing a min_pos variable in which is stored the index of the mininum number of the array in a particular step of a for loop :

void selectionsort(int A[], int n)
{
   for (int i = 0; i < n - 1; i  )
   {
       int min_pos = i;
       for (int j = i   1; j < n; j  )
       {
           if (A[j] < A[min_pos])
           {
               min_pos = j;
           }
           if (min_pos != i)
           {
               int temp;
               temp = A[i];
               A[i] = A[min_pos];
               A[min_pos] = temp;
           }
       }
   }
   return;
}

But, Is it necessary to introduce this variable when we can get the same result using the following code ?

void selectionsort(int A[], int n)
{
    for (int i = 0; i < n - 1; i  )
    {
        for (int j = i   1; j < n; j  )
        {
            if (A[j] < A[i])
            {
                int temp;
                temp = A[i];
                A[i] = A[j];
                A[j] = temp;
            }
        }
    }
    return;
}

CodePudding user response：

I think both algorithms are not particularly efficient, a more efficient way to write them would be as below:

void selectionsort(int A[], int n)
{
   for (int i = 0; i < n - 1; i  )
   {
       int min_pos = i;
       for (int j = i   1; j < n; j  )
       {
           if (A[j] < A[min_pos])
           {
               min_pos = j;
           }
       }
       if (min_pos != i)
       {
           int temp;
           temp = A[i];
           A[i] = A[min_pos];
           A[min_pos] = temp;
       }
   }
   return;
}

Notice how the min_pos variable is used as a temporary storage for the swapping position. This is beneficial since the swapping requires three operations while using min_pos only requires one operation.

CodePudding user response：

Both functions achieve the same result but neither one is a correct implementation of selection sort. They implement a less efficient algorithm called exchange sort.

For selection sort, a single swap should be performed for each element in the array. This was probably the purpose of the min_pos variable in the first function.

Here is a modified version:

void selectionsort(int A[], int n)
{
   for (int i = 0; i < n - 1; i  )
   {
       int min_pos = i;
       for (int j = i   1; j < n; j  )
       {
           if (A[j] < A[min_pos])
           {
               min_pos = j;
           }
       }
       if (min_pos != i)
       {
           int temp = A[i];
           A[i] = A[min_pos];
           A[min_pos] = temp;
       }
   }
}