Ndtyjky

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 Sortingn" );

     printf( "23 8 4 7 22 18 39 42 5 88 16 11 3n" );



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;

}

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.

There are almost no redeeming qualities in bubble sort, the nicest thing about it is its name. Donald Knuth has said that

the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems

And indeed, from Wikipedia about selection sort:

Among simple average-case Θ(n²) algorithms, selection sort almost always outperforms bubble sort and gnome sort.

There is no variation in selection sort - its running time does not depend on the ordering. For another good simple O(n²) algorithm that has variable running time, see insertion sort.