sorting the sorted array with selection algorithm with time complexity 0(1)

Question

if array is sorted then how to stop sorting .Time complexity 0(1) for the sorted array by selection sort.

static void sort(int a[]){
   int min;
     for(int i=0;i<a.length-1;i++){
         min=i;
         for(int j=i+1;j<a.length;j++)
         {

             if(a[j]<a[min])
                 min=j;

         }
         if(min==0){
             System.out.print("min" + min);
             break;
         }
         int temp=a[min];
         a[min]=a[i];
         a[i]=temp;

     }
    System.out.print(Arrays.toString(a) );

 }

Answer 1

What you have there is a Selection sort, which does not lend itself easily to an "early out" when the array is sorted.

Think about what it's doing:

1. Find the smallest item in the array and place it in position 0.
2. Find the smallest remaining item and place it in position 1.
3. Repeat, finding the kth smallest item and placing it in position k, until k = n.

The algorithm doesn't make any comparisons to see if the rest of the array is in order.

I suppose you could add such a thing:

static void sort(int a[]) {
   for(int i=0;i<a.length-1;i++){
       Boolean isSorted = true;
       Boolean didExchange = false;
       int min=i;
       for(int j=i+1;j<a.length;j++)
       {
           if(a[j]<a[min])
           {
               min=j;
           }
           if (a[j] < a[j-1])
           {
               // if at any point an item is smaller than its predecessor,
               // then the array is not sorted.
               isSorted = false;
           }
       }
       if (min != i)
       {
           didExchange = true;
           int temp=a[min];
           a[min]=a[i];
           a[i]=temp;
       }
       // If no exchange was made, and isSorted is still true,
       // then the array is sorted.
       if (isSorted && !didExchange)
       {
           break;
       }
   }
   System.out.print(Arrays.toString(a) );

}

That makes for some messy code. Selection sort is among the most inefficient of the standard O(n^2) sorting algorithms. Both Bubble sort and Insertion sort have better real-world performance, and both much more easily modified to detect an already sorted array. In fact, you don't need to modify Insertion sort at all; the "early out" is just part of the basic algorithm.

By the way, even if the array is sorted, this will require O(n). You can't determine if an array is sorted in O(1), because you have to examine all n items.