Can a selection sort algorithm terminate from its loop early the way a bubble sort is able to?

Question

This program will run fine if I do not include the early termination flag, but it only needs 10 sort passes to fully sort the list, not the full 12. However, when the termination flag is included, it terminates the sorting too early. Following the logic, I can see that this happens because after the third pass the array is ordered like this:

with the index i currently at 7, there are no lesser values to swap it with, so the flag does not get a value of 1 assigned to it and the loop terminates. So I guess my question is, is it possible to break out of a selection sort algorithm early and still fully complete the sort?

#include<stdio.h>
int main()
{
     int list[13]= {23,8,4,7,22,18,39,42,5,88,16,11,3};
     int temp,min,flag;
     printf( "Before Sorting\n" );
     printf( "23 8 4 7 22 18 39 42 5 88 16 11 3\n" );

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

        for( int j=i+1; j<13; j++ )
            {
                if( list[j]<list[min] )
                    {
                        flag = 1;
                        min = j  ;
                    }
            }

        if( !flag )
            break;

        temp = list[i];
        list[i]=list[min];
        list[min]=temp;

        printf( "\nAfter Pass %d.\n",i+1 );
        for( int i=0; i<13; i++ )
            printf( "%d ",list[i] );

        printf( "\n" );
    }

return 0;
}

Answer 1

Indeed you can. Here is such an implementation,

int selsort(int v[], int n){

  bool sorted = false; // v not known to be sorted
  int  i = 0;          // i smallest elements in place 

  while(!sorted){
    // find min v[i..n-1]
    // check if v[i..n-1] is sorted

    int  j   = i+1;
    int  min = i;    // position of minimum of v[i..j-1]
    sorted   = true; // v[i..j-1] sorted

    while(j<n){
      if(v[j]<v[min]) min = j;        // update min
      if(v[j]<v[j-1]) sorted = false; // update sorted
      j++;
    }

    if (!sorted){
      // place min v[i..n-1] in v[i]
      int aux = v[i];
      v[i]    = v[min];
      v[min]  = aux;      

      i++;
    }
  }

  return EXIT_SUCCESS;
}

As usual, in iteration i we start with v[0..i-1] sorted with the i smallest elements of the array in the correct place. So we want to find the min v[i..n-1] to put in position i. In this variant, as we do that we also check if v[i..n-1] is sorted. If it is sorted then there is nothing else to do.

Your implementation

In your implementation, the way you test for an ordered segment is wrong.

if( list[j]<list[min] )
    {
        flag = 1;
        min = j  ;
    }

Your flag will stay at 0 as long as you don't have to update the minimum in the inner loop. So any segment with the minimum in the first position will be considered sorted.