Selection Sort With Generics Implementation in Java

Selection Sort :

     Selection Sort is an elementary sorting algorithm with O(n^2) running time in worst case.

A Real Life Example Illustrating Selection Sort :

    Consider you have a pile of electricity bills for the past year, and you want to arrange them in ascending order from staring from January. One approach might be to look through the pile until you find the bill for January and pull that out. Then look through the remaining pile until you find the bill for February and add that behind January. Proceed through the ever-shrinking pile of bills to select next one until you are done. This is the inspiration for our Selection Sort.

How Selection Sort Works ?

     Just like all elementary sorting algorithms , Selection Sort also contains a double for loop. For every i th iteration of outer for loop, Selection Sort "selects" smallest element in the array, places it into position i. In other words, Selection sort finds the smallest element key in an unsorted list, then the second smallest element and so on.

When compared to the remaining elementary sorting algorithms, Selection Sort has few swaps. Finding the next smallest key requires searching through the entire unsorted portion of the array, but only one swap is required to put the record in the correct place. Thus the total number of swaps required will be n.

for i = 1 to n 

   minPos = i

   for j = i+1 to n

        if(a [ minPos] > a[j] 

            minPos = j

    end

    swap(a,minPos,i)

end

A Very Simple Implementation Of Selection Sort :

public void selectionSort(int[] inpArray) {
 int minIndex, temp;

 for(int i = 0; i < inpArray.length; i++) {

  minIndex = i;

  /*
   * This inner loop is for finding position of smallest 
                 * element in each iteration
   */

  for(int j = i+1; j < inpArray.length ; j++) {
   if(inpArray[minIndex] > inpArray[j]) {
    minIndex = j;
   }
  }
  
  /*
   * Swapping smallest element to bottom of the input Array. 
   * i.e smallest element to index 0, 2nd smallest element to  
                 * index 1 and so on.
   */

  temp = inpArray[i];
  inpArray[i] = inpArray[minIndex];
  inpArray[minIndex] = temp;
  printArray(inpArray);
 } 
   }
}

Implementation Of Selection Sort That Supports Generic Array In Java :

public < E extends Comparable < E >> void selectionSort(E[] inpArray) {

 int minIndex;
 E temp;

 for(int i = 0; i < inpArray.length; i++) {
  
              minIndex = i;
       for(int j = i+1; j < inpArray.length; j++) {
  if(inpArray[minIndex].compareTo(inpArray[j]) > 0) {
   minIndex = j;
  }
       }
  
       temp = inpArray[minIndex];
       inpArray[minIndex] = inpArray[i];
       inpArray[i] = temp;
 }
 
 for(E ele:inpArray) {
       System.out.print(ele.toString() + " ");
 }
 System.out.println();
}

Properties Of Selection Sort :

1. O(1) extra space in swapping.
2. O(n^2) time complexity in Best, Worst, and Average cases.
3. O(n) swaps

When To Use Selection Sort ?

    Because of O(n^2) worst case running time, Selection Sort is not used in practice. How ever, Selection Sort is advantageous when the cost to do a swap is high, for example, when the elements are long strings or large objects. Selection Sort is more efficient than Bubble Sort in most other situations as well.

Measuring Time Complexity Of Selection Sort ? 

    In Selection Sort, the outer for loop executes for n times, where n is size of the input. For every time, the inner for loop executes for one time less than its previous iteration. There fore the time complexity is

(n -1) +(n - 2) + (n - 3) + ..........+ 1 = (n-1) (n) / 2 = O(n^2) .

The number of iterations and comparisons are always same irrespective of the order and number of elements of input array. Hence the above computed time complexity holds for Best, Worst & Average case.