Selection Sort – Tailenders Technologies

Prerequisite:

Algorithm , Sorting , Asymptotic complexity(Time & Space Complexity)

Introduction :

If someone gives you a list to sort and we are not aware of various sorting algorithm, most of us will write the below code,

Code:

 public int[] doSelectionSort(int[] ip) {  
      int temp = 0;  
      for(int i=0;i<ip.length-1;i++) {  
           temp = i;  
           for(int j=i+1;j<ip.length;j++) {  
                if(ip[j]<ip[temp]) {  
                     temp = j;  
                }  
           }  
           if(i!=temp) {  
                swap(ip, i, temp);  
           }  
      }  
      return ip;  
 }

Performance:

Time complexity of this sorting is O(n²) regardless of worst or best case. It requires O(1) auxiliary space regardless of any case. It has relatively poor performance than others.

Where/When to use:

The only use of this algorithm is that it is easy to implement. But we may use it in few places. for instance, we have less than 10 elements in the list or we need only top 5 records out of 1000 or more records.
You may get some confusion that why i said we can use this sorting to find the top 5 record out of 1000 elements. Because we will be having 5*1000 comparison & we can skip the remaining comparisons in this sorting whereas insertion sort and merge sort has to execute all the comparisons with the time complexity O(n²) and O(n log n) respectively. You may think that bubble sort will also have the same 5*1000 comparison.But it needs more swap than the selection sort in a worst case scenario.