Selection Sort : Explained Along With Java Program Code

Sorting is  to place elements in increasing or decreasing order.  Selection sort  is a simple sorting algorithm .

The algorithm divides the input lists into two parts ; the sublist of the items are already sorted ,which is built up from left to right at the front(left) of the list , and the sublist of the  items remaining to be sorted that occupy the rest of the list. Initially the sorted sublist is empty and the unsorted sublist is the entire input list .The algorithm proceeds by finding the smallest (or largest depending on the sorting order ) element in the unsorted sublist  exchanging it with the leftmost unsorted element (putting in sorted order) and moving the sublist  boundaries one element to the right .

Read Also :      Bubble Sort Java Coding

It generally performs worst than the insertion sort though it has performance advantages over more complicated algorithms especially when auxiliary memory is limited .

When to Use

Selection sort is good to use for small number of input elements(less than 1000) . You can see  by running the below algorithm for
(Input)(Space)                           (Time taken)
10 elements           :           Selection sort took   0  milliseconds
100 elements         :           Selection sort took   0  milliseconds

1000 elements       :           Selection sort took   5  milliseconds 

10000 elements     :           Selection sort took   154 milliseconds
100000 elements   :           Selection sort took   13764  milliseconds


So , you can see it is not wise decision to use Selection sort for large number of elements as other algorithms take much less time .

Read Also  :       What is Servlet Class Hierarchy

Big O Notation

In simple words , Big O allows us to say something about how the size of inputs affect the runtime of a program .This technique can also be applied to other resources that an algorithm takes up (such as memory)
and we can analyze other bounds than the upper bound such as lower bound on time or space or expected time or space that an algorithm takes up .

Properties

* It is not a  Stable algorithm i.e does change the relative order of elements with equal keys

Best , Average,Worst Cases

*  Best Case        :    O(n^2)
* Average Case   :    O(n^2)
* Worst Case      :    O(n^2)

Demo here :

The code is given below :

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;

public class SelectionSort {
    
    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    public static int[] selectionSort(int[] list) {
        for (int i = 0; i < list.length - 1; i++) {
            // Find the index of the minimum value
            int minPos = i;
            for (int j = i + 1; j < list.length; j++) {
                if (list[j] < list[minPos]) {
                    minPos = j;
                }
            }
            swap(list, minPos, i);
        }
        return list;
    }
    
    
    
    public static void main(String args[]) throws Exception
    {
        String list="";
        int i=0,n=0;
        
        SelectionSort s= new SelectionSort();
        ArrayList<Integer> arrlist=new ArrayList<Integer>();
        System.out.println(" ");
        System.out.println(" ");
        System.out.println("Please enter the list of elements,one element per line");
        System.out.println(" write 'STOP' when list is completed ");
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        while(!(list=bf.readLine()).equalsIgnoreCase("stop")){
            int intelement=Integer.parseInt(list);
            arrlist.add(intelement);
            
        }
        
        int elementlist[]  = new int[arrlist.size()];
        Iterator<Integer> iter = arrlist.iterator();
        for (int j=0;iter.hasNext();j++) {
            elementlist[j] = iter.next();
        }
        
        elementlist=selectionSort(elementlist);
        System.out.println(" ");
        System.out.println(" ");
        System.out.println(" ");
        System.out.println("Values after Selection Sort : ");
        for (int j=0;j<elementlist.length;j++) {
            System.out.println(elementlist[j]+" ");
        }
    }
}